normalization/compose.mbt1///|2/// UTF-16 output of NFC and NFKC after the first suspect character, and the3/// segment being composed.4///5/// A segment begins at a starter that may compose with what follows and6/// ends before the next clean starter (CCC=0, Quick_Check=Yes), which never7/// composes with anything before it. The segment holds full decompositions8/// as packed entries, like those of `@decomposition.packed_decomposition`,9/// so composing it needs no further lookup of combining classes.10priv struct Composer {11 out : CodeUnits12 mut segment : FixedArray[Int32]13 mut segment_len : Int3214 /// The CCC of the last entry of the segment.15 mut previous_ccc : Int3216 mut needs_order : Bool17}1819///|20/// A composer writing to a buffer of `capacity` code units.21fn Composer::new(capacity : Int32) -> Composer {22 {23 out: CodeUnits::new(capacity),24 segment: FixedArray::make(32, 0),25 segment_len: 0,26 previous_ccc: 0,27 needs_order: false,28 }29}3031///|32#inline(never)33fn Composer::grow_segment(self : Composer) -> Unit {34 self.segment = FixedArray::make_and_blit(35 self.segment,36 allocate_len=2 * self.segment.length(),37 init=0,38 len=self.segment_len,39 )40}4142///|43/// Add one packed entry with combining class `ccc` to the segment.44fn Composer::push(self : Composer, entry : Int32, ccc : Int32) -> Unit {45 if self.segment_len == self.segment.length() {46 self.grow_segment()47 }48 if ccc != 0 && self.previous_ccc > ccc {49 self.needs_order = true50 }51 self.previous_ccc = ccc52 // SAFETY: the segment has room after `segment_len`, as checked above.53 self.segment.unsafe_set(self.segment_len, entry)54 self.segment_len += 155}5657///|58/// Add a character with normalization record `record` to the segment,59/// decomposed when it has a decomposition of this form's kind.60///61/// Hangul syllables stay whole: an LV syllable composes with a following62/// trailing jamo as its decomposition would, and nothing else composes with63/// either. Conjoining jamo compose here, as soon as they arrive: a leading64/// jamo never composes with what precedes it, and a vowel or trailing jamo65/// right after the starter it composes with is never blocked or reordered.66/// This is common, not only for compatibility jamo: a clean run often ends67/// at a leading jamo, which then begins a segment.68fn Composer::append(69 self : Composer,70 code_point : Int32,71 record : Int32,72 compatibility~ : Bool,73) -> Unit {74 let decomposition_bit = if compatibility { 13 } else { 12 }75 let c = code_point.unsafe_to_char()76 if ((record >> decomposition_bit) & 1) == 0 || is_hangul_syllable(c) {77 let ccc = record & 25578 if ccc == 0 && self.segment_len > 0 && self.previous_ccc == 0 {79 // SAFETY: the segment is not empty.80 let last = self.segment.unsafe_get(self.segment_len - 1)81 if try_compose_hangul(last.unsafe_to_char(), c) is Some(syllable) {82 self.segment.unsafe_set(self.segment_len - 1, syllable.to_int())83 return84 }85 }86 self.push(code_point | (ccc << PackedCccShift), ccc)87 } else {88 for entry in @decomposition.packed_decomposition(record, compatibility~) {89 self.push(entry, entry >> PackedCccShift)90 }91 }92}9394///|95/// Sort each run of nonstarters of the segment by CCC, keeping equal96/// classes in their order.97fn Composer::order_segment(self : Composer) -> Unit {98 let segment = self.segment99 // SAFETY: every index is below segment_len <= segment.length().100 for i in 1..<self.segment_len {101 let entry = segment.unsafe_get(i)102 let ccc = entry >> PackedCccShift103 if ccc == 0 {104 continue105 }106 // A starter's class is 0, below any nonstarter's, so the insertion107 // stops at the start of the run.108 let mut j = i109 while j > 0 && segment.unsafe_get(j - 1) >> PackedCccShift > ccc {110 segment.unsafe_set(j, segment.unsafe_get(j - 1))111 j -= 1112 }113 segment.unsafe_set(j, entry)114 }115}116117///|118/// Apply the canonical composition algorithm to the segment in place.119fn Composer::compose_segment(self : Composer) -> Unit {120 let segment = self.segment121 let len = self.segment_len122 // SAFETY: the segment is not empty, every read index is below len <=123 // segment.length(), and written <= i, last_starter < written.124 let first_ccc = segment.unsafe_get(0) >> PackedCccShift125 // The last starter kept, or -1 before the first.126 let mut last_starter = if first_ccc == 0 { 0 } else { -1 }127 // The CCC of the last entry kept; a composed entry keeps the starter's.128 let mut last_ccc = first_ccc129 let mut written = 1130 for i in 1..<len {131 let entry = segment.unsafe_get(i)132 let ccc = entry >> PackedCccShift133 // A character is blocked from the last starter by any character kept134 // between them whose class is 0 or not below its own.135 let blocked = last_ccc != 0 && (ccc == 0 || last_ccc >= ccc)136 if last_starter >= 0 && !blocked {137 let starter = (segment.unsafe_get(last_starter) & PackedCodePointMask).unsafe_to_char()138 let second = (entry & PackedCodePointMask).unsafe_to_char()139 if try_compose(starter, second) is Some(composed) {140 // Composites are starters, so the entry's class stays 0.141 segment.unsafe_set(last_starter, composed.to_int())142 continue143 }144 }145 segment.unsafe_set(written, entry)146 written += 1147 if ccc == 0 {148 last_starter = written - 1149 }150 last_ccc = ccc151 }152 self.segment_len = written153}154155///|156/// Compose the segment and write it out.157fn Composer::flush(self : Composer) -> Unit {158 if self.segment_len == 0 {159 return160 }161 if self.segment_len > 1 {162 if self.needs_order {163 self.order_segment()164 }165 self.compose_segment()166 }167 self.out.reserve(2 * self.segment_len)168 for i in 0..<self.segment_len {169 self.out.store(self.segment[i] & PackedCodePointMask)170 }171 self.segment_len = 0172 self.previous_ccc = 0173 self.needs_order = false174}175176///|177/// Whether composing the segment leaves `span`, its characters in the178/// input, as they are. The segment is then cleared.179fn Composer::check(self : Composer, span : StringView) -> Bool {180 if self.segment_len > 1 {181 if self.needs_order {182 self.order_segment()183 }184 self.compose_segment()185 }186 let segment = self.segment187 let len = self.segment_len188 let mut i = 0189 let mut unchanged = true190 for c in span {191 // SAFETY: i < len <= segment.length().192 if i >= len || (segment.unsafe_get(i) & PackedCodePointMask) != c.to_int() {193 unchanged = false194 break195 }196 i += 1197 }198 self.segment_len = 0199 self.previous_ccc = 0200 self.needs_order = false201 unchanged && i == len202}203204///|205/// Compose `s` from view-relative `start`, the last starter before the206/// first suspect character (or the view's start). Everything before `start`207/// is unchanged. The record bits from `shift` hold this form's Quick_Check208/// value, and `compatibility` selects NFKC.209///210/// Like `decompose_remaining`, this copies clean runs as they are, found by211/// the clean-run scanner, except for each run's last character: the212/// characters after it may compose with it, so it begins a segment.213#inline(never)214fn compose_remaining(215 s : StringView,216 start : Int32,217 shift : Int32,218 compatibility~ : Bool,219) -> String {220 let data = s.data()221 let view_start = s.start_offset()222 let view_end = view_start + s.length()223 let slow_mask = 255 | (ComposeQuickCheckMask << shift)224 // A literal rather than `Composer::new`: on wasm-gc, where moonc keeps225 // that a call, NFC measured up to 18% slower with it.226 let composer : Composer = {227 out: {228 data: FixedArray::make(s.length() + 16, 0),229 len: 0,230 marks_start: 0,231 previous_ccc: 0,232 needs_order: false,233 },234 segment: FixedArray::make(32, 0),235 segment_len: 0,236 previous_ccc: 0,237 needs_order: false,238 }239 composer.out.copy(data, view_start, view_start + start)240 let mut offset = view_start + start241 while offset < view_end {242 // A leading jamo is a clean starter, and it composes at once with the243 // vowel and trailing jamo right after it, before any lookup. An LVT244 // syllable composes with nothing that follows, so it is written out, and245 // so is an LV syllable in NFC: no canonical decomposition begins with a246 // trailing jamo. In NFKC an LV syllable begins a segment instead, since247 // a compatibility jamo that follows, such as U+3133, may decompose to a248 // trailing jamo that composes with it.249 // SAFETY: offset < view_end, and each following unit is read only below250 // view_end.251 let l_index = data.unsafe_get(offset).to_int() - hangul_l_base252 if l_index >= 0 && l_index < hangul_l_count && offset + 1 < view_end {253 let v_index = data.unsafe_get(offset + 1).to_int() - hangul_v_base254 if v_index >= 0 && v_index < hangul_v_count {255 composer.flush()256 let syllable = hangul_s_base +257 (l_index * hangul_v_count + v_index) * hangul_t_count258 offset += 2259 if offset < view_end {260 let t_index = data.unsafe_get(offset).to_int() - hangul_t_base261 if t_index > 0 && t_index < hangul_t_count {262 composer.out.reserve(1)263 composer.out.store(syllable + t_index)264 offset += 1265 continue266 }267 }268 if compatibility {269 composer.push(syllable, 0)270 } else {271 composer.out.reserve(1)272 composer.out.store(syllable)273 }274 continue275 }276 }277 let code_point = code_point_at(data, offset, view_end)278 let width = if code_point >= 0x10000 { 2 } else { 1 }279 // An unpaired surrogate has default properties: a clean starter.280 let record = normalization_record(code_point.unsafe_to_char())281 if (record & 255) != 0 || ((record >> shift) & 3) != 0 {282 composer.append(code_point, record, compatibility~)283 offset += width284 continue285 }286 // A clean starter: nothing from here on composes with the segment.287 composer.flush()288 let run_end = scan_clean_run(data, offset + width, view_end, slow_mask)289 if run_end == view_end {290 composer.out.copy(data, offset, view_end)291 break292 }293 // The run's last character begins the next segment.294 let mut last = run_end - 1295 if last > offset &&296 data.unsafe_get(last).is_trailing_surrogate() &&297 data.unsafe_get(last - 1).is_leading_surrogate() {298 last -= 1299 }300 if last == offset {301 composer.append(code_point, record, compatibility~)302 } else {303 composer.out.copy(data, offset, last)304 let last_code_point = code_point_at(data, last, view_end)305 composer.append(306 last_code_point,307 normalization_record(last_code_point.unsafe_to_char()),308 compatibility~,309 )310 }311 offset = run_end312 }313 composer.flush()314 // Copied here for the reasons given in `decompose_remaining`.315 let out = composer.out316 if ArrayOfNumbers {317 return code_units_prefix_to_string(out.data, out.len)318 }319 let result = FixedArray::make(out.len, (0).to_uint16())320 result.unsafe_blit(0, out.data, 0, out.len)321 uint16_array_to_string(result)322}323324///|325/// The code point at absolute `offset` of `s`, where `end` bounds the units326/// that may be read. An unpaired surrogate is returned as it is.327fn code_point_at(s : String, offset : Int32, end : Int32) -> Int32 {328 // SAFETY: the caller passes offset < end <= s.length().329 let unit = s.unsafe_get(offset).to_int()330 if unit >= 0xD800 && unit <= 0xDBFF && offset + 1 < end {331 let trail = s.unsafe_get(offset + 1).to_int()332 if trail >= 0xDC00 && trail <= 0xDFFF {333 return 0x10000 + ((unit - 0xD800) << 10) + trail - 0xDC00334 }335 }336 unit337}338
///|
/// UTF-16 output of NFC and NFKC after the first suspect character, and the
/// segment being composed.
///
/// A segment begins at a starter that may compose with what follows and
/// ends before the next clean starter (CCC=0, Quick_Check=Yes), which never
/// composes with anything before it. The segment holds full decompositions
/// as packed entries, like those of `@decomposition.packed_decomposition`,
/// so composing it needs no further lookup of combining classes.
priv struct Composer {
out : CodeUnits
mut segment : FixedArray[Int32]
mut segment_len : Int32
/// The CCC of the last entry of the segment.
mut previous_ccc : Int32
mut needs_order : Bool
}
///|
/// A composer writing to a buffer of `capacity` code units.
fn Composer::new(capacity : Int32) -> Composer {
{
out: CodeUnits::new(capacity),
segment: FixedArray::make(32, 0),
segment_len: 0,
previous_ccc: 0,
needs_order: false,
}
}
///|
#inline(never)
fn Composer::grow_segment(self : Composer) -> Unit {
self.segment = FixedArray::make_and_blit(
self.segment,
allocate_len=2 * self.segment.length(),
init=0,
len=self.segment_len,
)
}
///|
/// Add one packed entry with combining class `ccc` to the segment.
fn Composer::push(self : Composer, entry : Int32, ccc : Int32) -> Unit {
if self.segment_len == self.segment.length() {
self.grow_segment()
}
if ccc != 0 && self.previous_ccc > ccc {
self.needs_order = true
}
self.previous_ccc = ccc
// SAFETY: the segment has room after `segment_len`, as checked above.
self.segment.unsafe_set(self.segment_len, entry)
self.segment_len += 1
}
///|
/// Add a character with normalization record `record` to the segment,
/// decomposed when it has a decomposition of this form's kind.
///
/// Hangul syllables stay whole: an LV syllable composes with a following
/// trailing jamo as its decomposition would, and nothing else composes with
/// either. Conjoining jamo compose here, as soon as they arrive: a leading
/// jamo never composes with what precedes it, and a vowel or trailing jamo
/// right after the starter it composes with is never blocked or reordered.
/// This is common, not only for compatibility jamo: a clean run often ends
/// at a leading jamo, which then begins a segment.
fn Composer::append(
self : Composer,
code_point : Int32,
record : Int32,
compatibility~ : Bool,
) -> Unit {
let decomposition_bit = if compatibility { 13 } else { 12 }
let c = code_point.unsafe_to_char()
if ((record >> decomposition_bit) & 1) == 0 || is_hangul_syllable(c) {
let ccc = record & 255
if ccc == 0 && self.segment_len > 0 && self.previous_ccc == 0 {
// SAFETY: the segment is not empty.
let last = self.segment.unsafe_get(self.segment_len - 1)
if try_compose_hangul(last.unsafe_to_char(), c) is Some(syllable) {
self.segment.unsafe_set(self.segment_len - 1, syllable.to_int())
return
}
}
self.push(code_point | (ccc << PackedCccShift), ccc)
} else {
for entry in @decomposition.packed_decomposition(record, compatibility~) {
self.push(entry, entry >> PackedCccShift)
}
}
}
///|
/// Sort each run of nonstarters of the segment by CCC, keeping equal
/// classes in their order.
fn Composer::order_segment(self : Composer) -> Unit {
let segment = self.segment
// SAFETY: every index is below segment_len <= segment.length().
for i in 1..<self.segment_len {
let entry = segment.unsafe_get(i)
let ccc = entry >> PackedCccShift
if ccc == 0 {
continue
}
// A starter's class is 0, below any nonstarter's, so the insertion
// stops at the start of the run.
let mut j = i
while j > 0 && segment.unsafe_get(j - 1) >> PackedCccShift > ccc {
segment.unsafe_set(j, segment.unsafe_get(j - 1))
j -= 1
}
segment.unsafe_set(j, entry)
}
}
///|
/// Apply the canonical composition algorithm to the segment in place.
fn Composer::compose_segment(self : Composer) -> Unit {
let segment = self.segment
let len = self.segment_len
// SAFETY: the segment is not empty, every read index is below len <=
// segment.length(), and written <= i, last_starter < written.
let first_ccc = segment.unsafe_get(0) >> PackedCccShift
// The last starter kept, or -1 before the first.
let mut last_starter = if first_ccc == 0 { 0 } else { -1 }
// The CCC of the last entry kept; a composed entry keeps the starter's.
let mut last_ccc = first_ccc
let mut written = 1
for i in 1..<len {
let entry = segment.unsafe_get(i)
let ccc = entry >> PackedCccShift
// A character is blocked from the last starter by any character kept
// between them whose class is 0 or not below its own.
let blocked = last_ccc != 0 && (ccc == 0 || last_ccc >= ccc)
if last_starter >= 0 && !blocked {
let starter = (segment.unsafe_get(last_starter) & PackedCodePointMask).unsafe_to_char()
let second = (entry & PackedCodePointMask).unsafe_to_char()
if try_compose(starter, second) is Some(composed) {
// Composites are starters, so the entry's class stays 0.
segment.unsafe_set(last_starter, composed.to_int())
continue
}
}
segment.unsafe_set(written, entry)
written += 1
if ccc == 0 {
last_starter = written - 1
}
last_ccc = ccc
}
self.segment_len = written
}
///|
/// Compose the segment and write it out.
fn Composer::flush(self : Composer) -> Unit {
if self.segment_len == 0 {
return
}
if self.segment_len > 1 {
if self.needs_order {
self.order_segment()
}
self.compose_segment()
}
self.out.reserve(2 * self.segment_len)
for i in 0..<self.segment_len {
self.out.store(self.segment[i] & PackedCodePointMask)
}
self.segment_len = 0
self.previous_ccc = 0
self.needs_order = false
}
///|
/// Whether composing the segment leaves `span`, its characters in the
/// input, as they are. The segment is then cleared.
fn Composer::check(self : Composer, span : StringView) -> Bool {
if self.segment_len > 1 {
if self.needs_order {
self.order_segment()
}
self.compose_segment()
}
let segment = self.segment
let len = self.segment_len
let mut i = 0
let mut unchanged = true
for c in span {
// SAFETY: i < len <= segment.length().
if i >= len || (segment.unsafe_get(i) & PackedCodePointMask) != c.to_int() {
unchanged = false
break
}
i += 1
}
self.segment_len = 0
self.previous_ccc = 0
self.needs_order = false
unchanged && i == len
}
///|
/// Compose `s` from view-relative `start`, the last starter before the
/// first suspect character (or the view's start). Everything before `start`
/// is unchanged. The record bits from `shift` hold this form's Quick_Check
/// value, and `compatibility` selects NFKC.
///
/// Like `decompose_remaining`, this copies clean runs as they are, found by
/// the clean-run scanner, except for each run's last character: the
/// characters after it may compose with it, so it begins a segment.
#inline(never)
fn compose_remaining(
s : StringView,
start : Int32,
shift : Int32,
compatibility~ : Bool,
) -> String {
let data = s.data()
let view_start = s.start_offset()
let view_end = view_start + s.length()
let slow_mask = 255 | (ComposeQuickCheckMask << shift)
// A literal rather than `Composer::new`: on wasm-gc, where moonc keeps
// that a call, NFC measured up to 18% slower with it.
let composer : Composer = {
out: {
data: FixedArray::make(s.length() + 16, 0),
len: 0,
marks_start: 0,
previous_ccc: 0,
needs_order: false,
},
segment: FixedArray::make(32, 0),
segment_len: 0,
previous_ccc: 0,
needs_order: false,
}
composer.out.copy(data, view_start, view_start + start)
let mut offset = view_start + start
while offset < view_end {
// A leading jamo is a clean starter, and it composes at once with the
// vowel and trailing jamo right after it, before any lookup. An LVT
// syllable composes with nothing that follows, so it is written out, and
// so is an LV syllable in NFC: no canonical decomposition begins with a
// trailing jamo. In NFKC an LV syllable begins a segment instead, since
// a compatibility jamo that follows, such as U+3133, may decompose to a
// trailing jamo that composes with it.
// SAFETY: offset < view_end, and each following unit is read only below
// view_end.
let l_index = data.unsafe_get(offset).to_int() - hangul_l_base
if l_index >= 0 && l_index < hangul_l_count && offset + 1 < view_end {
let v_index = data.unsafe_get(offset + 1).to_int() - hangul_v_base
if v_index >= 0 && v_index < hangul_v_count {
composer.flush()
let syllable = hangul_s_base +
(l_index * hangul_v_count + v_index) * hangul_t_count
offset += 2
if offset < view_end {
let t_index = data.unsafe_get(offset).to_int() - hangul_t_base
if t_index > 0 && t_index < hangul_t_count {
composer.out.reserve(1)
composer.out.store(syllable + t_index)
offset += 1
continue
}
}
if compatibility {
composer.push(syllable, 0)
} else {
composer.out.reserve(1)
composer.out.store(syllable)
}
continue
}
}
let code_point = code_point_at(data, offset, view_end)
let width = if code_point >= 0x10000 { 2 } else { 1 }
// An unpaired surrogate has default properties: a clean starter.
let record = normalization_record(code_point.unsafe_to_char())
if (record & 255) != 0 || ((record >> shift) & 3) != 0 {
composer.append(code_point, record, compatibility~)
offset += width
continue
}
// A clean starter: nothing from here on composes with the segment.
composer.flush()
let run_end = scan_clean_run(data, offset + width, view_end, slow_mask)
if run_end == view_end {
composer.out.copy(data, offset, view_end)
break
}
// The run's last character begins the next segment.
let mut last = run_end - 1
if last > offset &&
data.unsafe_get(last).is_trailing_surrogate() &&
data.unsafe_get(last - 1).is_leading_surrogate() {
last -= 1
}
if last == offset {
composer.append(code_point, record, compatibility~)
} else {
composer.out.copy(data, offset, last)
let last_code_point = code_point_at(data, last, view_end)
composer.append(
last_code_point,
normalization_record(last_code_point.unsafe_to_char()),
compatibility~,
)
}
offset = run_end
}
composer.flush()
// Copied here for the reasons given in `decompose_remaining`.
let out = composer.out
if ArrayOfNumbers {
return code_units_prefix_to_string(out.data, out.len)
}
let result = FixedArray::make(out.len, (0).to_uint16())
result.unsafe_blit(0, out.data, 0, out.len)
uint16_array_to_string(result)
}
///|
/// The code point at absolute `offset` of `s`, where `end` bounds the units
/// that may be read. An unpaired surrogate is returned as it is.
fn code_point_at(s : String, offset : Int32, end : Int32) -> Int32 {
// SAFETY: the caller passes offset < end <= s.length().
let unit = s.unsafe_get(offset).to_int()
if unit >= 0xD800 && unit <= 0xDBFF && offset + 1 < end {
let trail = s.unsafe_get(offset + 1).to_int()
if trail >= 0xDC00 && trail <= 0xDFFF {
return 0x10000 + ((unit - 0xD800) << 10) + trail - 0xDC00
}
}
unit
}