unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

normalization/decompose.mbt
1///|2/// The fields of an entry of `@decomposition.packed_decomposition`.3const PackedCodePointMask : Int32 = 0x1FFFFF45///|6const PackedCccShift : Int32 = 2178///|9/// Take ownership of UTF-16 code units as a string of the same length.10fn uint16_array_to_string(buffer : FixedArray[UInt16]) -> String = "%string.unsafe_from_uint16_fixedarray"1112///|13/// Whether a `FixedArray` is an array of numbers, as on JS, so that the14/// prefix of the output buffer converts to a string without a copy.15#cfg(target="js")16const ArrayOfNumbers : Bool = true1718///|19#cfg(not(target="js"))20const ArrayOfNumbers : Bool = false2122///|23/// The first `len` code units of `data` as a string, on JS. `len` is at most24/// `data.length()`.25///26/// The exact-length copy that the other backends need costs about 3 ns per27/// code unit on JS, since `FixedArray::unsafe_blit` copies element by element28/// there; that was over a quarter of NFD's time on Cyrillic text.29#cfg(target="js")30extern "js" fn code_units_prefix_to_string(31  data : FixedArray[UInt16],32  len : Int32,33) -> String =34  #|(data, len) => {35  #|  let result = "";36  #|  for (let i = 0; i < len; i += 8192) {37  #|    result += String.fromCharCode.apply(null, data.slice(i, Math.min(i + 8192, len)));38  #|  }39  #|  return result;40  #|}4142///|43/// Never called off JS, where `ArrayOfNumbers` is false.44#cfg(not(target="js"))45fn code_units_prefix_to_string(46  data : FixedArray[UInt16],47  len : Int32,48) -> String {49  ignore(data)50  ignore(len)51  ""52}5354///|55/// UTF-16 output, owned until it becomes a string.56///57/// NFD and NFKD write their output here as it is produced, after the first58/// suspect character, with no scratch segment: decomposition never merges59/// characters, so each can be written as soon as it is decomposed. The60/// trailing run of nonstarters is tracked so that it is sorted in place, and61/// only when it is out of order. NFC and NFKC write segments that are already62/// composed and ordered, and leave that state alone.63priv struct CodeUnits {64  mut data : FixedArray[UInt16]65  mut len : Int3266  /// Where the trailing run of nonstarters begins.67  mut marks_start : Int3268  /// The CCC of the last unit written if it ends a nonstarter, else 0.69  mut previous_ccc : Int3270  mut needs_order : Bool71}7273///|74fn CodeUnits::new(capacity : Int32) -> CodeUnits {75  {76    data: FixedArray::make(capacity, 0),77    len: 0,78    marks_start: 0,79    previous_ccc: 0,80    needs_order: false,81  }82}8384///|85#inline(never)86fn CodeUnits::grow(self : CodeUnits, required : Int32) -> Unit {87  let mut capacity = if self.data.length() < 16 {88    1689  } else {90    2 * self.data.length()91  }92  while capacity < required {93    capacity *= 294  }95  self.data = FixedArray::make_and_blit(96    self.data,97    allocate_len=capacity,98    init=0,99    len=self.len,100  )101}102103///|104/// Make room for `count` more code units.105fn CodeUnits::reserve(self : CodeUnits, count : Int32) -> Unit {106  if self.len + count > self.data.length() {107    self.grow(self.len + count)108  }109}110111///|112/// Store one code point. The caller has reserved two units.113fn CodeUnits::store(self : CodeUnits, code_point : Int32) -> Unit {114  // SAFETY: the caller reserved two units after `len`.115  if code_point < 0x10000 {116    self.data.unsafe_set(self.len, code_point.to_uint16())117    self.len += 1118  } else {119    let offset = code_point - 0x10000120    self.data.unsafe_set(self.len, (0xD800 + (offset >> 10)).to_uint16())121    self.data.unsafe_set(self.len + 1, (0xDC00 + (offset & 0x3FF)).to_uint16())122    self.len += 2123  }124}125126///|127/// Copy code units `start` to `end` of `s` unchanged.128fn CodeUnits::copy(129  self : CodeUnits,130  s : String,131  start : Int32,132  end : Int32,133) -> Unit {134  let count = end - start135  self.reserve(count)136  // Locals, so that the stores need not reload the fields: the C backend137  // does not assume that stores of code units leave this record unchanged.138  let data = self.data139  let len = self.len140  // SAFETY: the caller passes 0 <= start <= end <= s.length(), and `count`141  // units are reserved after `len`.142  for i in 0..<count {143    data.unsafe_set(len + i, s.unsafe_get(start + i))144  }145  self.len = len + count146}147148///|149/// End the trailing run of nonstarters before a starter is written.150fn CodeUnits::end_marks(self : CodeUnits) -> Unit {151  if self.needs_order {152    self.reorder_marks()153    self.needs_order = false154  }155  self.previous_ccc = 0156}157158///|159/// Sort the trailing run of nonstarters by CCC, keeping equal classes in160/// their order. Marks out of order are rare, so this decodes and looks up161/// again rather than keeping the classes around.162#inline(never)163fn CodeUnits::reorder_marks(self : CodeUnits) -> Unit {164  let marks : Array[Char] = []165  let mut i = self.marks_start166  while i < self.len {167    let unit = self.data[i].to_int()168    if unit >= 0xD800 && unit <= 0xDBFF && i + 1 < self.len {169      let trail = self.data[i + 1].to_int()170      marks.push(171        (0x10000 + ((unit - 0xD800) << 10) + trail - 0xDC00).unsafe_to_char(),172      )173      i += 2174    } else {175      marks.push(unit.unsafe_to_char())176      i += 1177    }178  }179  canonical_order(marks)180  self.len = self.marks_start181  for c in marks {182    self.store(c.to_int())183  }184}185186///|187/// Store one fully decomposed character with combining class `ccc`. The188/// caller has reserved two units.189fn CodeUnits::emit(self : CodeUnits, code_point : Int32, ccc : Int32) -> Unit {190  if ccc == 0 {191    if self.previous_ccc != 0 {192      self.end_marks()193    }194  } else if self.previous_ccc == 0 {195    self.marks_start = self.len196    self.previous_ccc = ccc197  } else {198    if self.previous_ccc > ccc {199      self.needs_order = true200    }201    self.previous_ccc = ccc202  }203  self.store(code_point)204}205206///|207/// Decompose `s` from view-relative `start`, the last starter before the208/// first suspect character (or the view's start). Everything before `start`209/// is unchanged.210///211/// Clean starters (CCC=0, Quick_Check=Yes) are their own decomposition, and212/// no mark reorders across a starter, so clean runs are copied as they are.213/// The clean-run scanner finds where each ends: it reads a table without214/// calls, much cheaper per character than a property lookup, so it pays215/// even for the single starters between marks.216#inline(never)217fn decompose_remaining(218  s : StringView,219  start : Int32,220  shift : Int32,221  compatibility~ : Bool,222) -> String {223  let data = s.data()224  let view_start = s.start_offset()225  let view_end = view_start + s.length()226  let slow_mask = 255 | (1 << shift)227  let out = CodeUnits::new(s.length() + s.length() / 2 + 16)228  out.copy(data, view_start, view_start + start)229  let mut offset = view_start + start230  while offset < view_end {231    // Decoded here rather than by `code_point_at`, which moonc keeps a call232    // on wasm-gc: there, the call made Korean NFD 14% slower.233    // SAFETY: view_start <= offset < view_end <= data.length(), and the234    // trailing unit is read only when offset + 1 < view_end.235    let unit = data.unsafe_get(offset).to_int()236    let mut code_point = unit237    let mut width = 1238    if unit >= 0xD800 && unit <= 0xDBFF && offset + 1 < view_end {239      let trail = data.unsafe_get(offset + 1).to_int()240      if trail >= 0xDC00 && trail <= 0xDFFF {241        code_point = 0x10000 + ((unit - 0xD800) << 10) + trail - 0xDC00242        width = 2243      }244    }245    // An unpaired surrogate has default properties: a clean starter.246    let c = code_point.unsafe_to_char()247    let record = normalization_record(c)248    let ccc = record & 255249    out.reserve(2)250    if ((record >> shift) & 1) == 0 {251      if ccc != 0 {252        out.emit(code_point, ccc)253      } else {254        let run_end = scan_clean_run(data, offset + width, view_end, slow_mask)255        out.emit(code_point, 0)256        out.copy(data, offset + width, run_end)257        offset = run_end258        continue259      }260    } else if is_hangul_syllable(c) {261      // Conjoining jamo are starters.262      if out.previous_ccc != 0 {263        out.end_marks()264      }265      out.reserve(3)266      let s_index = code_point - hangul_s_base267      let t_index = s_index % hangul_t_count268      // Conjoining jamo are in the BMP: one unit each, stored through269      // locals as in `CodeUnits::copy`.270      let units = out.data271      let len = out.len272      // SAFETY: three units are reserved after `len`.273      units.unsafe_set(274        len,275        (hangul_l_base + s_index / hangul_n_count).to_uint16(),276      )277      units.unsafe_set(278        len + 1,279        (hangul_v_base + s_index % hangul_n_count / hangul_t_count).to_uint16(),280      )281      if t_index != 0 {282        units.unsafe_set(len + 2, (hangul_t_base + t_index).to_uint16())283        out.len = len + 3284      } else {285        out.len = len + 2286      }287    } else {288      // The character has a mapping of this form's kind, so the view is not289      // empty, and its entries carry their combining classes.290      let entries = @decomposition.packed_decomposition(record, compatibility~)291      out.reserve(2 * entries.length())292      for entry in entries {293        out.emit(entry & PackedCodePointMask, entry >> PackedCccShift)294      }295    }296    offset += width297  }298  if out.previous_ccc != 0 {299    out.end_marks()300  }301  if ArrayOfNumbers {302    return code_units_prefix_to_string(out.data, out.len)303  }304  // The result is copied here rather than in a function: on wasm-gc, where305  // moonc keeps such a function a call, NFD measured 10-20% slower with it,306  // though the loop compiled to the same instructions.307  let result = FixedArray::make(out.len, (0).to_uint16())308  result.unsafe_blit(0, out.data, 0, out.len)309  uint16_array_to_string(result)310}311