///|
/// 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()
}
}