normalization/quick_check.mbt1///|2/// The normalization record of a character: its packed properties in bits3/// 0..15, and in the bits above, where `@decomposition.packed_decomposition`4/// finds its decomposition. ASCII has CCC=0, Quick_Check=Yes for every5/// normalization form and no decomposition.6fn normalization_record(c : Char) -> Int32 {7 if c.to_int() < 0x80 {8 09 } else {10 @decomposition.lookup_normalization_record(c)11 }12}1314///|15/// The Quick_Check bits of NFC and NFKC, the forms that compose: Yes=0,16/// No=1, Maybe=2.17const ComposeQuickCheckMask : Int32 = 31819///|20/// Check suspect segments of NFC or NFKC, composed in `composer`, until a21/// clean run. Return its next unconsumed boundary, or -1 if checking fails.22fn check_suspect_spans(23 composer : Composer,24 s : StringView,25 start : Int32,26 problem_offset : Int32,27 shift : Int32,28 compatibility~ : Bool,29) -> Int32 {30 // Retain the starter and any preceding marks in the first suspect segment.31 for c in s[start:problem_offset] {32 composer.append(c.to_int(), normalization_record(c), compatibility~)33 }34 let mut span_start = start35 let mut offset = problem_offset36 let mut previous_ccc = 037 let mut suspect = true38 let mut clean_start = problem_offset39 for c in s[problem_offset:] {40 let record = normalization_record(c)41 let ccc = record & 25542 let check = (record >> shift) & ComposeQuickCheckMask43 if ccc == 0 && check == 0 {44 // Amortize the handoff over a clean run: consume up to two UTF-16 units45 // here before resuming the tight scanner. Dense one/two-starter gaps46 // stay in this loop, reusing their already loaded properties.47 if !suspect && previous_ccc == 0 && offset - clean_start >= 2 {48 return offset49 }50 if suspect {51 if !composer.check(s[span_start:offset]) {52 return -153 }54 clean_start = offset55 }56 span_start = offset57 suspect = false58 }59 let out_of_order = ccc != 0 && previous_ccc > ccc60 if check == 1 || out_of_order {61 return -162 }63 if !suspect && check != 0 {64 for preceding in s[span_start:offset] {65 composer.append(66 preceding.to_int(),67 normalization_record(preceding),68 compatibility~,69 )70 }71 suspect = true72 }73 if suspect {74 composer.append(c.to_int(), record, compatibility~)75 }76 previous_ccc = ccc77 offset += if c.to_int() > 0xFFFF { 2 } else { 1 }78 }79 if suspect && !composer.check(s[span_start:offset]) {80 return -181 }82 offset83}8485///|86/// Skip Quick_Check=Yes, CCC=0 characters from `start` and return the offset87/// of the first other character. Without one before `end`, return `end`, or88/// one past it when a surrogate pair crosses it. `slow_mask` selects CCC and89/// one form's Quick_Check bits of the packed properties; shifted right by90/// seven it selects the same bits of the generated scan flags.91/// Offsets are absolute in the backing string. `limit` is the view's end;92/// a pair may cross the current scan chunk's `end`, but never `limit`.93///94/// The loop reads the generated one-byte flags and makes no calls. Looking95/// properties up through `@ccc` instead costs a call per character, because96/// functions are not inlined across packages. Even one call on a rare path97/// would make every entry to this function save and restore registers, which98/// shows on text with many short runs. The loop is also sensitive to its99/// shape: trying blocks inside it instead of around it costs an extra taken100/// branch per character.101fn scan_clean_units(102 s : String,103 start : Int32,104 end : Int32,105 limit : Int32,106 slow_mask : Int32,107) -> Int32 {108 let scan_mask = slow_mask >> 7109 let unit_mask = scan_mask | NormalizationScanLeadSurrogate110 let mut offset = start111 while offset < end {112 // SAFETY: offset starts at a nonnegative boundary and offset < end <= limit <= s.length().113 // It advances by two only after checking that a second unit exists.114 let first = s.unsafe_get(offset).to_int()115 // SAFETY: first is a UTF-16 code unit, so first >> NormalizationScanShift116 // indexes one of the 2048 blocks; the generator checks every flags index.117 let block = normalization_scan_index118 .unsafe_get(first >> NormalizationScanShift)119 .to_int()120 let flags = normalization_scan_flags121 .unsafe_get(122 (block << NormalizationScanShift) | (first & NormalizationScanBlockMask),123 )124 .to_int()125 if (flags & unit_mask) == 0 {126 offset += 1127 continue128 }129 if flags != NormalizationScanLeadSurrogate {130 break131 }132 // An unpaired surrogate has default properties.133 if offset + 1 >= limit {134 offset += 1135 continue136 }137 // SAFETY: offset + 1 < limit is checked above.138 let second = s.unsafe_get(offset + 1).to_int()139 if second < 0xDC00 || second > 0xDFFF {140 offset += 1141 continue142 }143 let lead = first - 0xD800144 // Compare the default-tail boundary before reading the group summary.145 // SAFETY: a valid pair outside that tail has a generated lead index.146 if lead > NormalizationTailLeadIndex ||147 (lead == NormalizationTailLeadIndex && second >= NormalizationTailTrail) ||148 (normalization_lead_flags.unsafe_get(lead).to_int() & scan_mask) == 0 {149 offset += 2150 continue151 }152 // Some character in this group of 1024 has flags: read this pair's own.153 // SAFETY: lead is below the tail as above and trail is a 10-bit value;154 // the generator checks both indices for every such pair.155 let trail = second - 0xDC00156 let slot = normalization_lead_slots.unsafe_get(lead).to_int()157 let pair_block = normalization_pair_index158 .unsafe_get(159 (slot << (10 - NormalizationPairShift)) |160 (trail >> NormalizationPairShift),161 )162 .to_int()163 let pair_flags = normalization_pair_flags164 .unsafe_get(165 (pair_block << NormalizationPairShift) |166 (trail & NormalizationPairBlockMask),167 )168 .to_int()169 if (pair_flags & scan_mask) != 0 {170 break171 }172 offset += 2173 }174 offset175}176177///|178/// Return the end of the run of clean characters starting at `start`.179///180/// Once a stretch of code units has passed the scan one at a time, blocks181/// are tried: a block whose code units are all below the clean limit needs182/// no table. The stretch starts short, so that a run that soon ends never183/// reaches a block, and grows while no block is clean, so that text above the184/// limit pays for few tries and few calls. On native and wasm, later185/// stretches are scanned four units at a time, which takes fewer branches per186/// unit but costs more where the run ends, so the first stretch, where most187/// short runs end, is not.188fn scan_clean_run(189 s : String,190 start : Int32,191 end : Int32,192 slow_mask : Int32,193) -> Int32 {194 let mut offset = start195 let mut stretch = MinUnitStretch196 while true {197 let chunk_end = if end - offset > stretch { offset + stretch } else { end }198 if offset > start {199 offset = skip_clean_quads(s, offset, chunk_end, slow_mask >> 7)200 }201 offset = scan_clean_units(s, offset, chunk_end, end, slow_mask)202 // A pair that crosses `chunk_end` leaves the offset one past it.203 if offset < chunk_end || offset >= end {204 break205 }206 let blocks_end = skip_clean_blocks(s, offset, end, slow_mask >> 7)207 if blocks_end > offset {208 stretch = MinUnitStretch209 } else if stretch < MaxUnitStretch {210 stretch = 4 * stretch211 }212 offset = blocks_end213 }214 offset215}216217///|218/// Without SIMD, the scan one unit at a time is faster than groups of four.219#cfg(not(any(target="native", target="wasm")))220fn skip_clean_quads(221 _s : String,222 start : Int32,223 _end : Int32,224 _scan_mask : Int32,225) -> Int32 {226 start227}228229///|230/// Skip groups of four code units that are all clean. A lead surrogate231/// stops the skip; the scan one unit at a time handles it.232#cfg(any(target="native", target="wasm"))233fn skip_clean_quads(234 s : String,235 start : Int32,236 end : Int32,237 scan_mask : Int32,238) -> Int32 {239 let unit_mask = scan_mask | NormalizationScanLeadSurrogate240 let mut offset = start241 while end - offset >= 4 {242 // SAFETY: four units remain before `end`.243 let flags = unit_scan_flags(s.unsafe_get(offset)) |244 unit_scan_flags(s.unsafe_get(offset + 1)) |245 unit_scan_flags(s.unsafe_get(offset + 2)) |246 unit_scan_flags(s.unsafe_get(offset + 3))247 if (flags & unit_mask) != 0 {248 break249 }250 offset += 4251 }252 offset253}254255///|256/// The scan flags of one code unit.257#cfg(any(target="native", target="wasm"))258fn unit_scan_flags(unit : UInt16) -> Int32 {259 let unit = unit.to_int()260 // SAFETY: a code unit shifted by NormalizationScanShift indexes one of the261 // 2048 blocks; the generator checks every flags index.262 normalization_scan_flags263 .unsafe_get(264 (265 normalization_scan_index266 .unsafe_get(unit >> NormalizationScanShift)267 .to_int() <<268 NormalizationScanShift269 ) |270 (unit & NormalizationScanBlockMask),271 )272 .to_int()273}274275///|276/// Code units scanned one at a time before the first block and after a block277/// that is not clean.278const MinUnitStretch : Int32 = 16279280///|281const MaxUnitStretch : Int32 = 4096282283///|284/// The first code unit that is not a clean starter in the forms `scan_mask`285/// selects: U+00A0 has a compatibility mapping, U+00C0 a canonical one, and286/// U+0300 is the first combining mark. The wasm-gc skip tests the287/// `scan_mask` bits inline instead.288#cfg(not(target="wasm-gc"))289fn clean_unit_limit(scan_mask : Int32) -> Int32 {290 if (scan_mask & 0b1011000) != 0 {291 0xA0292 } else if (scan_mask & 0b0100000) != 0 {293 0xC0294 } else {295 0x300296 }297}298299///|300/// Skip blocks of four code units that are all below the clean limit, and301/// return the offset of the first block that is not, or that is incomplete.302/// Without SIMD, comparing the units' union is one test per block, against303/// the largest power of two at or below the limit: U+0200 for NFC, which304/// covers Latin Extended-A, and ASCII for the other forms.305#cfg(target="wasm-gc")306fn skip_clean_blocks(307 s : String,308 start : Int32,309 end : Int32,310 scan_mask : Int32,311) -> Int32 {312 // `clean_unit_limit` is 0x300 exactly when none of these forms is selected.313 // Tested here, since a call stays a call on wasm-gc: calling it made NFD314 // 6-8% slower there on x86.315 let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }316 let mut offset = start317 while end - offset >= 4 {318 // SAFETY: four units remain before `end`.319 let units = s.unsafe_get(offset) |320 s.unsafe_get(offset + 1) |321 s.unsafe_get(offset + 2) |322 s.unsafe_get(offset + 3)323 if units.to_int() >= limit {324 break325 }326 offset += 4327 }328 offset329}330331///|332/// The loop of the wasm-gc `skip_clean_blocks`, for a JS view that ends333/// before its string.334#cfg(target="js")335fn skip_low_unit_blocks(336 s : String,337 start : Int32,338 end : Int32,339 scan_mask : Int32,340) -> Int32 {341 // The test of the wasm-gc version, for the same `scan_mask` bits.342 let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }343 let mut offset = start344 while end - offset >= 4 {345 // SAFETY: four units remain before `end`.346 let units = s.unsafe_get(offset) |347 s.unsafe_get(offset + 1) |348 s.unsafe_get(offset + 2) |349 s.unsafe_get(offset + 3)350 if units.to_int() >= limit {351 break352 }353 offset += 4354 }355 offset356}357358///|359/// Skip code units that are all below the clean limit, and return the offset360/// of the first that is not. A sticky regular expression scans the string in361/// V8's compiled matcher, about three times as fast on ASCII as reading the362/// units one at a time; it stops only at a unit it rejects or at the string's363/// end, so a view that ends early is scanned with the loop instead.364#cfg(target="js")365fn skip_clean_blocks(366 s : String,367 start : Int32,368 end : Int32,369 scan_mask : Int32,370) -> Int32 {371 let limit = clean_unit_limit(scan_mask)372 // SAFETY: start < end is checked first. A run often ends at its first373 // unit, as in Cyrillic text, and the call into the matcher costs more374 // than that test.375 if start >= end || s.unsafe_get(start).to_int() >= limit {376 start377 } else if end == s.length() {378 skip_units_below(s, start, limit)379 } else {380 skip_low_unit_blocks(s, start, end, scan_mask)381 }382}383384///|385/// The offset of the first code unit of `s` from `start` that is not below386/// `limit`, one of the results of `clean_unit_limit`, or `s.length()`.387#cfg(target="js")388extern "js" fn skip_units_below(389 s : String,390 start : Int32,391 limit : Int32,392) -> Int32 =393 #|(() => {394 #| const below = { 0xa0: /[\0-\x9f]*/y, 0xc0: /[\0-\xbf]*/y, 0x300: /[\0-\u02ff]*/y };395 #| return (s, start, limit) => {396 #| const re = below[limit];397 #| re.lastIndex = start;398 #| re.test(s);399 #| return re.lastIndex;400 #| };401 #|})()402403///|404/// Skip blocks of eight code units that are all below the clean limit, and405/// return the offset of the first block that is not, or that is incomplete.406///407/// A unit at or above the limit is the one that leaves a lane nonzero after408/// subtracting `limit - 1` with saturation. That takes one instruction on409/// SSE2, which has no unsigned 16-bit comparison, and two blocks are tested410/// per step. With a comparison and one block per step, the loop took 60-86%411/// longer on the x86 CI runners (AMD EPYC 7763 and 9V74) once a change to412/// unrelated tables moved it, though its code was the same: about 4 cycles413/// per block instead of 2.5.414#cfg(target="native")415// The SIMD operations are experimental upstream. Only this function uses416// them, so the alert is silenced here and not for the whole package.417#warnings("-alert_experimental")418fn skip_clean_blocks(419 s : String,420 start : Int32,421 end : Int32,422 scan_mask : Int32,423) -> Int32 {424 let below = @v128.i16x8_splat((clean_unit_limit(scan_mask) - 1).to_uint16())425 let mut offset = start426 while end - offset >= 16 {427 // SAFETY: offset is absolute and sixteen units remain before the view's428 // end.429 let excess = @v128.v128_or_(430 @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below),431 @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset + 8), below),432 )433 if @v128.v128_any_true(excess) {434 break435 }436 offset += 16437 }438 // The first block of a pair that failed may still be clean.439 while end - offset >= 8 {440 // SAFETY: offset is absolute and eight units remain before the view's end.441 let excess = @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below)442 if @v128.v128_any_true(excess) {443 break444 }445 offset += 8446 }447 offset448}449450///|451/// Skip blocks of eight code units that are all below the clean limit, and452/// return the offset of the first block that is not, or that is incomplete.453///454/// The native version tests two blocks per step; here that made NFD on455/// Cyrillic text 30-38% slower in V8, though it halved the time on ASCII.456#cfg(target="wasm")457// The SIMD operations are experimental upstream. Only this function uses458// them, so the alert is silenced here and not for the whole package.459#warnings("-alert_experimental")460fn skip_clean_blocks(461 s : String,462 start : Int32,463 end : Int32,464 scan_mask : Int32,465) -> Int32 {466 let limit = @v128.i16x8_splat(clean_unit_limit(scan_mask).to_uint16())467 let mut offset = start468 while end - offset >= 8 {469 // SAFETY: offset is absolute and eight units remain before the view's end.470 let block = @v128.v128_load_i16x8(s, offset)471 if @v128.v128_any_true(@v128.i16x8_ge_u(block, limit)) {472 break473 }474 offset += 8475 }476 offset477}478479///|480/// Scan UTF-16 with one cursor. The clean-run scan only skips Quick_Check=Yes,481/// CCC=0 characters; CCC ordering and boundary recovery live outside that loop.482/// When it stops, the last skipped code point is the preceding safe boundary.483/// Checking returns None on a difference and Some("") on success, without484/// copying the input. Normalization returns Some with the normalized string.485/// String? uses the native nullable-pointer representation; StringView? would486/// allocate an Option wrapper even when the input is already normalized.487fn process_spans(488 s : StringView,489 shift : Int32,490 mask : Int32,491 compatibility~ : Bool,492 compose~ : Bool,493 check_only~ : Bool,494) -> String? {495 let data = s.data()496 let start = s.start_offset()497 let end = start + s.length()498 let slow_mask = 255 | (mask << shift)499 let mut offset = start500 let mut span_start = start501 let mut previous_ccc = 0502 while offset < end {503 let run_start = offset504 offset = scan_clean_run(data, offset, end, slow_mask)505 if offset == end {506 return Some(if check_only { "" } else { s.to_owned() })507 }508 // SAFETY: start <= offset < end <= data.length().509 let mut cp = data.unsafe_get(offset).to_int()510 let mut width = 1511 if cp >= 0xD800 && cp <= 0xDBFF {512 // The scan stops on a leading surrogate only when a trailing one follows.513 cp = 0x10000 + ((cp - 0xD800) << 10) + data[offset + 1].to_int() - 0xDC00514 width = 2515 }516 let properties = @ccc.lookup_normalization_properties(cp.unsafe_to_char())517 if offset > run_start {518 // All skipped characters are CCC=0 and Quick_Check=Yes. Recover only519 // the last one's start, including its leading surrogate when present.520 // Written out, not shared with the other two scans that do this: a521 // helper stays a call on wasm-gc, where this runs after every clean522 // run.523 span_start = offset - 1524 if data[span_start].is_trailing_surrogate() &&525 span_start > run_start &&526 data[span_start - 1].is_leading_surrogate() {527 span_start -= 1528 }529 previous_ccc = 0530 }531 let ccc = properties & 255532 let check = (properties >> shift) & mask533 let out_of_order = ccc != 0 && previous_ccc > ccc534 if check_only && (check == 1 || out_of_order) {535 return None536 }537 if check != 0 || out_of_order {538 if !check_only {539 let remaining_start = span_start - start540 return Some(541 if compose {542 compose_remaining(s, remaining_start, shift, compatibility~)543 } else {544 decompose_remaining(s, remaining_start, shift, compatibility~)545 },546 )547 }548 // Checking reaches this point only past Quick_Check=Maybe, which549 // only NFC and NFKC have.550 return if check_remaining_spans(551 s,552 span_start - start,553 offset - start,554 shift,555 compatibility~,556 ) {557 Some("")558 } else {559 None560 }561 }562 // Quick_Check=Yes marks still require ordering checks. Keep their starter563 // boundary until the next run of CCC=0 characters or a suspect character.564 previous_ccc = ccc565 offset += width566 }567 Some(if check_only { "" } else { s.to_owned() })568}569570///|571/// Check NFC or NFKC after the first suspect character, reusing one572/// composer, which writes nothing. Normal runs resume the tight scanner; the573/// allocation-free entry path keeps the scratch state out of its hot loop.574fn check_remaining_spans(575 s : StringView,576 start : Int32,577 problem_offset : Int32,578 shift : Int32,579 compatibility~ : Bool,580) -> Bool {581 let composer = Composer::new(0)582 let length = s.length()583 let data = s.data()584 let view_start = s.start_offset()585 let view_end = view_start + length586 let slow_mask = 255 | (ComposeQuickCheckMask << shift)587 let mut offset = problem_offset588 let mut span_start = start589 while offset < length {590 offset = check_suspect_spans(591 composer,592 s,593 span_start,594 offset,595 shift,596 compatibility~,597 )598 if offset < 0 {599 return false600 }601 // The helper stopped before a clean starter (or at the end). Scan the602 // following run without carrying scratch state through its loop.603 let run_start = offset604 // Suspect-segment processing uses view-relative offsets; convert only605 // at the handoff to the scanner, whose hot loop uses absolute offsets.606 offset = scan_clean_run(data, view_start + offset, view_end, slow_mask) -607 view_start608 if offset == length {609 break610 }611 // At least one clean starter was skipped. Retain its last code point for612 // the next segment, including the leading half of a surrogate pair.613 span_start = offset - 1614 if s[span_start].is_trailing_surrogate() &&615 span_start > run_start &&616 s[span_start - 1].is_leading_surrogate() {617 span_start -= 1618 }619 }620 true621}622623///|624fn normalize_spans(625 s : StringView,626 shift : Int32,627 mask : Int32,628 compatibility~ : Bool,629 compose~ : Bool,630) -> String {631 // Keep the fallback lazy without allocating a capturing closure.632 if process_spans(s, shift, mask, compatibility~, compose~, check_only=false)633 is Some(result) {634 result635 } else {636 s.to_owned()637 }638}639
///|
/// The normalization record of a character: its packed properties in bits
/// 0..15, and in the bits above, where `@decomposition.packed_decomposition`
/// finds its decomposition. ASCII has CCC=0, Quick_Check=Yes for every
/// normalization form and no decomposition.
fn normalization_record(c : Char) -> Int32 {
if c.to_int() < 0x80 {
0
} else {
@decomposition.lookup_normalization_record(c)
}
}
///|
/// The Quick_Check bits of NFC and NFKC, the forms that compose: Yes=0,
/// No=1, Maybe=2.
const ComposeQuickCheckMask : Int32 = 3
///|
/// Check suspect segments of NFC or NFKC, composed in `composer`, until a
/// clean run. Return its next unconsumed boundary, or -1 if checking fails.
fn check_suspect_spans(
composer : Composer,
s : StringView,
start : Int32,
problem_offset : Int32,
shift : Int32,
compatibility~ : Bool,
) -> Int32 {
// Retain the starter and any preceding marks in the first suspect segment.
for c in s[start:problem_offset] {
composer.append(c.to_int(), normalization_record(c), compatibility~)
}
let mut span_start = start
let mut offset = problem_offset
let mut previous_ccc = 0
let mut suspect = true
let mut clean_start = problem_offset
for c in s[problem_offset:] {
let record = normalization_record(c)
let ccc = record & 255
let check = (record >> shift) & ComposeQuickCheckMask
if ccc == 0 && check == 0 {
// Amortize the handoff over a clean run: consume up to two UTF-16 units
// here before resuming the tight scanner. Dense one/two-starter gaps
// stay in this loop, reusing their already loaded properties.
if !suspect && previous_ccc == 0 && offset - clean_start >= 2 {
return offset
}
if suspect {
if !composer.check(s[span_start:offset]) {
return -1
}
clean_start = offset
}
span_start = offset
suspect = false
}
let out_of_order = ccc != 0 && previous_ccc > ccc
if check == 1 || out_of_order {
return -1
}
if !suspect && check != 0 {
for preceding in s[span_start:offset] {
composer.append(
preceding.to_int(),
normalization_record(preceding),
compatibility~,
)
}
suspect = true
}
if suspect {
composer.append(c.to_int(), record, compatibility~)
}
previous_ccc = ccc
offset += if c.to_int() > 0xFFFF { 2 } else { 1 }
}
if suspect && !composer.check(s[span_start:offset]) {
return -1
}
offset
}
///|
/// Skip Quick_Check=Yes, CCC=0 characters from `start` and return the offset
/// of the first other character. Without one before `end`, return `end`, or
/// one past it when a surrogate pair crosses it. `slow_mask` selects CCC and
/// one form's Quick_Check bits of the packed properties; shifted right by
/// seven it selects the same bits of the generated scan flags.
/// Offsets are absolute in the backing string. `limit` is the view's end;
/// a pair may cross the current scan chunk's `end`, but never `limit`.
///
/// The loop reads the generated one-byte flags and makes no calls. Looking
/// properties up through `@ccc` instead costs a call per character, because
/// functions are not inlined across packages. Even one call on a rare path
/// would make every entry to this function save and restore registers, which
/// shows on text with many short runs. The loop is also sensitive to its
/// shape: trying blocks inside it instead of around it costs an extra taken
/// branch per character.
fn scan_clean_units(
s : String,
start : Int32,
end : Int32,
limit : Int32,
slow_mask : Int32,
) -> Int32 {
let scan_mask = slow_mask >> 7
let unit_mask = scan_mask | NormalizationScanLeadSurrogate
let mut offset = start
while offset < end {
// SAFETY: offset starts at a nonnegative boundary and offset < end <= limit <= s.length().
// It advances by two only after checking that a second unit exists.
let first = s.unsafe_get(offset).to_int()
// SAFETY: first is a UTF-16 code unit, so first >> NormalizationScanShift
// indexes one of the 2048 blocks; the generator checks every flags index.
let block = normalization_scan_index
.unsafe_get(first >> NormalizationScanShift)
.to_int()
let flags = normalization_scan_flags
.unsafe_get(
(block << NormalizationScanShift) | (first & NormalizationScanBlockMask),
)
.to_int()
if (flags & unit_mask) == 0 {
offset += 1
continue
}
if flags != NormalizationScanLeadSurrogate {
break
}
// An unpaired surrogate has default properties.
if offset + 1 >= limit {
offset += 1
continue
}
// SAFETY: offset + 1 < limit is checked above.
let second = s.unsafe_get(offset + 1).to_int()
if second < 0xDC00 || second > 0xDFFF {
offset += 1
continue
}
let lead = first - 0xD800
// Compare the default-tail boundary before reading the group summary.
// SAFETY: a valid pair outside that tail has a generated lead index.
if lead > NormalizationTailLeadIndex ||
(lead == NormalizationTailLeadIndex && second >= NormalizationTailTrail) ||
(normalization_lead_flags.unsafe_get(lead).to_int() & scan_mask) == 0 {
offset += 2
continue
}
// Some character in this group of 1024 has flags: read this pair's own.
// SAFETY: lead is below the tail as above and trail is a 10-bit value;
// the generator checks both indices for every such pair.
let trail = second - 0xDC00
let slot = normalization_lead_slots.unsafe_get(lead).to_int()
let pair_block = normalization_pair_index
.unsafe_get(
(slot << (10 - NormalizationPairShift)) |
(trail >> NormalizationPairShift),
)
.to_int()
let pair_flags = normalization_pair_flags
.unsafe_get(
(pair_block << NormalizationPairShift) |
(trail & NormalizationPairBlockMask),
)
.to_int()
if (pair_flags & scan_mask) != 0 {
break
}
offset += 2
}
offset
}
///|
/// Return the end of the run of clean characters starting at `start`.
///
/// Once a stretch of code units has passed the scan one at a time, blocks
/// are tried: a block whose code units are all below the clean limit needs
/// no table. The stretch starts short, so that a run that soon ends never
/// reaches a block, and grows while no block is clean, so that text above the
/// limit pays for few tries and few calls. On native and wasm, later
/// stretches are scanned four units at a time, which takes fewer branches per
/// unit but costs more where the run ends, so the first stretch, where most
/// short runs end, is not.
fn scan_clean_run(
s : String,
start : Int32,
end : Int32,
slow_mask : Int32,
) -> Int32 {
let mut offset = start
let mut stretch = MinUnitStretch
while true {
let chunk_end = if end - offset > stretch { offset + stretch } else { end }
if offset > start {
offset = skip_clean_quads(s, offset, chunk_end, slow_mask >> 7)
}
offset = scan_clean_units(s, offset, chunk_end, end, slow_mask)
// A pair that crosses `chunk_end` leaves the offset one past it.
if offset < chunk_end || offset >= end {
break
}
let blocks_end = skip_clean_blocks(s, offset, end, slow_mask >> 7)
if blocks_end > offset {
stretch = MinUnitStretch
} else if stretch < MaxUnitStretch {
stretch = 4 * stretch
}
offset = blocks_end
}
offset
}
///|
/// Without SIMD, the scan one unit at a time is faster than groups of four.
#cfg(not(any(target="native", target="wasm")))
fn skip_clean_quads(
_s : String,
start : Int32,
_end : Int32,
_scan_mask : Int32,
) -> Int32 {
start
}
///|
/// Skip groups of four code units that are all clean. A lead surrogate
/// stops the skip; the scan one unit at a time handles it.
#cfg(any(target="native", target="wasm"))
fn skip_clean_quads(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
let unit_mask = scan_mask | NormalizationScanLeadSurrogate
let mut offset = start
while end - offset >= 4 {
// SAFETY: four units remain before `end`.
let flags = unit_scan_flags(s.unsafe_get(offset)) |
unit_scan_flags(s.unsafe_get(offset + 1)) |
unit_scan_flags(s.unsafe_get(offset + 2)) |
unit_scan_flags(s.unsafe_get(offset + 3))
if (flags & unit_mask) != 0 {
break
}
offset += 4
}
offset
}
///|
/// The scan flags of one code unit.
#cfg(any(target="native", target="wasm"))
fn unit_scan_flags(unit : UInt16) -> Int32 {
let unit = unit.to_int()
// SAFETY: a code unit shifted by NormalizationScanShift indexes one of the
// 2048 blocks; the generator checks every flags index.
normalization_scan_flags
.unsafe_get(
(
normalization_scan_index
.unsafe_get(unit >> NormalizationScanShift)
.to_int() <<
NormalizationScanShift
) |
(unit & NormalizationScanBlockMask),
)
.to_int()
}
///|
/// Code units scanned one at a time before the first block and after a block
/// that is not clean.
const MinUnitStretch : Int32 = 16
///|
const MaxUnitStretch : Int32 = 4096
///|
/// The first code unit that is not a clean starter in the forms `scan_mask`
/// selects: U+00A0 has a compatibility mapping, U+00C0 a canonical one, and
/// U+0300 is the first combining mark. The wasm-gc skip tests the
/// `scan_mask` bits inline instead.
#cfg(not(target="wasm-gc"))
fn clean_unit_limit(scan_mask : Int32) -> Int32 {
if (scan_mask & 0b1011000) != 0 {
0xA0
} else if (scan_mask & 0b0100000) != 0 {
0xC0
} else {
0x300
}
}
///|
/// Skip blocks of four code units that are all below the clean limit, and
/// return the offset of the first block that is not, or that is incomplete.
/// Without SIMD, comparing the units' union is one test per block, against
/// the largest power of two at or below the limit: U+0200 for NFC, which
/// covers Latin Extended-A, and ASCII for the other forms.
#cfg(target="wasm-gc")
fn skip_clean_blocks(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
// `clean_unit_limit` is 0x300 exactly when none of these forms is selected.
// Tested here, since a call stays a call on wasm-gc: calling it made NFD
// 6-8% slower there on x86.
let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }
let mut offset = start
while end - offset >= 4 {
// SAFETY: four units remain before `end`.
let units = s.unsafe_get(offset) |
s.unsafe_get(offset + 1) |
s.unsafe_get(offset + 2) |
s.unsafe_get(offset + 3)
if units.to_int() >= limit {
break
}
offset += 4
}
offset
}
///|
/// The loop of the wasm-gc `skip_clean_blocks`, for a JS view that ends
/// before its string.
#cfg(target="js")
fn skip_low_unit_blocks(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
// The test of the wasm-gc version, for the same `scan_mask` bits.
let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }
let mut offset = start
while end - offset >= 4 {
// SAFETY: four units remain before `end`.
let units = s.unsafe_get(offset) |
s.unsafe_get(offset + 1) |
s.unsafe_get(offset + 2) |
s.unsafe_get(offset + 3)
if units.to_int() >= limit {
break
}
offset += 4
}
offset
}
///|
/// Skip code units that are all below the clean limit, and return the offset
/// of the first that is not. A sticky regular expression scans the string in
/// V8's compiled matcher, about three times as fast on ASCII as reading the
/// units one at a time; it stops only at a unit it rejects or at the string's
/// end, so a view that ends early is scanned with the loop instead.
#cfg(target="js")
fn skip_clean_blocks(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
let limit = clean_unit_limit(scan_mask)
// SAFETY: start < end is checked first. A run often ends at its first
// unit, as in Cyrillic text, and the call into the matcher costs more
// than that test.
if start >= end || s.unsafe_get(start).to_int() >= limit {
start
} else if end == s.length() {
skip_units_below(s, start, limit)
} else {
skip_low_unit_blocks(s, start, end, scan_mask)
}
}
///|
/// The offset of the first code unit of `s` from `start` that is not below
/// `limit`, one of the results of `clean_unit_limit`, or `s.length()`.
#cfg(target="js")
extern "js" fn skip_units_below(
s : String,
start : Int32,
limit : Int32,
) -> Int32 =
#|(() => {
#| const below = { 0xa0: /[\0-\x9f]*/y, 0xc0: /[\0-\xbf]*/y, 0x300: /[\0-\u02ff]*/y };
#| return (s, start, limit) => {
#| const re = below[limit];
#| re.lastIndex = start;
#| re.test(s);
#| return re.lastIndex;
#| };
#|})()
///|
/// Skip blocks of eight code units that are all below the clean limit, and
/// return the offset of the first block that is not, or that is incomplete.
///
/// A unit at or above the limit is the one that leaves a lane nonzero after
/// subtracting `limit - 1` with saturation. That takes one instruction on
/// SSE2, which has no unsigned 16-bit comparison, and two blocks are tested
/// per step. With a comparison and one block per step, the loop took 60-86%
/// longer on the x86 CI runners (AMD EPYC 7763 and 9V74) once a change to
/// unrelated tables moved it, though its code was the same: about 4 cycles
/// per block instead of 2.5.
#cfg(target="native")
// The SIMD operations are experimental upstream. Only this function uses
// them, so the alert is silenced here and not for the whole package.
#warnings("-alert_experimental")
fn skip_clean_blocks(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
let below = @v128.i16x8_splat((clean_unit_limit(scan_mask) - 1).to_uint16())
let mut offset = start
while end - offset >= 16 {
// SAFETY: offset is absolute and sixteen units remain before the view's
// end.
let excess = @v128.v128_or_(
@v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below),
@v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset + 8), below),
)
if @v128.v128_any_true(excess) {
break
}
offset += 16
}
// The first block of a pair that failed may still be clean.
while end - offset >= 8 {
// SAFETY: offset is absolute and eight units remain before the view's end.
let excess = @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below)
if @v128.v128_any_true(excess) {
break
}
offset += 8
}
offset
}
///|
/// Skip blocks of eight code units that are all below the clean limit, and
/// return the offset of the first block that is not, or that is incomplete.
///
/// The native version tests two blocks per step; here that made NFD on
/// Cyrillic text 30-38% slower in V8, though it halved the time on ASCII.
#cfg(target="wasm")
// The SIMD operations are experimental upstream. Only this function uses
// them, so the alert is silenced here and not for the whole package.
#warnings("-alert_experimental")
fn skip_clean_blocks(
s : String,
start : Int32,
end : Int32,
scan_mask : Int32,
) -> Int32 {
let limit = @v128.i16x8_splat(clean_unit_limit(scan_mask).to_uint16())
let mut offset = start
while end - offset >= 8 {
// SAFETY: offset is absolute and eight units remain before the view's end.
let block = @v128.v128_load_i16x8(s, offset)
if @v128.v128_any_true(@v128.i16x8_ge_u(block, limit)) {
break
}
offset += 8
}
offset
}
///|
/// Scan UTF-16 with one cursor. The clean-run scan only skips Quick_Check=Yes,
/// CCC=0 characters; CCC ordering and boundary recovery live outside that loop.
/// When it stops, the last skipped code point is the preceding safe boundary.
/// Checking returns None on a difference and Some("") on success, without
/// copying the input. Normalization returns Some with the normalized string.
/// String? uses the native nullable-pointer representation; StringView? would
/// allocate an Option wrapper even when the input is already normalized.
fn process_spans(
s : StringView,
shift : Int32,
mask : Int32,
compatibility~ : Bool,
compose~ : Bool,
check_only~ : Bool,
) -> String? {
let data = s.data()
let start = s.start_offset()
let end = start + s.length()
let slow_mask = 255 | (mask << shift)
let mut offset = start
let mut span_start = start
let mut previous_ccc = 0
while offset < end {
let run_start = offset
offset = scan_clean_run(data, offset, end, slow_mask)
if offset == end {
return Some(if check_only { "" } else { s.to_owned() })
}
// SAFETY: start <= offset < end <= data.length().
let mut cp = data.unsafe_get(offset).to_int()
let mut width = 1
if cp >= 0xD800 && cp <= 0xDBFF {
// The scan stops on a leading surrogate only when a trailing one follows.
cp = 0x10000 + ((cp - 0xD800) << 10) + data[offset + 1].to_int() - 0xDC00
width = 2
}
let properties = @ccc.lookup_normalization_properties(cp.unsafe_to_char())
if offset > run_start {
// All skipped characters are CCC=0 and Quick_Check=Yes. Recover only
// the last one's start, including its leading surrogate when present.
// Written out, not shared with the other two scans that do this: a
// helper stays a call on wasm-gc, where this runs after every clean
// run.
span_start = offset - 1
if data[span_start].is_trailing_surrogate() &&
span_start > run_start &&
data[span_start - 1].is_leading_surrogate() {
span_start -= 1
}
previous_ccc = 0
}
let ccc = properties & 255
let check = (properties >> shift) & mask
let out_of_order = ccc != 0 && previous_ccc > ccc
if check_only && (check == 1 || out_of_order) {
return None
}
if check != 0 || out_of_order {
if !check_only {
let remaining_start = span_start - start
return Some(
if compose {
compose_remaining(s, remaining_start, shift, compatibility~)
} else {
decompose_remaining(s, remaining_start, shift, compatibility~)
},
)
}
// Checking reaches this point only past Quick_Check=Maybe, which
// only NFC and NFKC have.
return if check_remaining_spans(
s,
span_start - start,
offset - start,
shift,
compatibility~,
) {
Some("")
} else {
None
}
}
// Quick_Check=Yes marks still require ordering checks. Keep their starter
// boundary until the next run of CCC=0 characters or a suspect character.
previous_ccc = ccc
offset += width
}
Some(if check_only { "" } else { s.to_owned() })
}
///|
/// Check NFC or NFKC after the first suspect character, reusing one
/// composer, which writes nothing. Normal runs resume the tight scanner; the
/// allocation-free entry path keeps the scratch state out of its hot loop.
fn check_remaining_spans(
s : StringView,
start : Int32,
problem_offset : Int32,
shift : Int32,
compatibility~ : Bool,
) -> Bool {
let composer = Composer::new(0)
let length = s.length()
let data = s.data()
let view_start = s.start_offset()
let view_end = view_start + length
let slow_mask = 255 | (ComposeQuickCheckMask << shift)
let mut offset = problem_offset
let mut span_start = start
while offset < length {
offset = check_suspect_spans(
composer,
s,
span_start,
offset,
shift,
compatibility~,
)
if offset < 0 {
return false
}
// The helper stopped before a clean starter (or at the end). Scan the
// following run without carrying scratch state through its loop.
let run_start = offset
// Suspect-segment processing uses view-relative offsets; convert only
// at the handoff to the scanner, whose hot loop uses absolute offsets.
offset = scan_clean_run(data, view_start + offset, view_end, slow_mask) -
view_start
if offset == length {
break
}
// At least one clean starter was skipped. Retain its last code point for
// the next segment, including the leading half of a surrogate pair.
span_start = offset - 1
if s[span_start].is_trailing_surrogate() &&
span_start > run_start &&
s[span_start - 1].is_leading_surrogate() {
span_start -= 1
}
}
true
}
///|
fn normalize_spans(
s : StringView,
shift : Int32,
mask : Int32,
compatibility~ : Bool,
compose~ : Bool,
) -> String {
// Keep the fallback lazy without allocating a capturing closure.
if process_spans(s, shift, mask, compatibility~, compose~, check_only=false)
is Some(result) {
result
} else {
s.to_owned()
}
}