unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

normalization/compose.mbt
1///|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