unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

tools/ucd/normalization.mbt
1///|2/// BMP lookups use one block-offset load and one norm16 value load.3const NormalizationBmpShift : Int32 = 545///|6const NormalizationBmpLimit : Int32 = 0x1000078///|9/// Supplementary top blocks cover 128 code points; leaves hold four values.10const NormalizationTopShift : Int32 = 71112///|13const NormalizationLeafShift : Int32 = 21415///|16/// Pack CCC and Quick_Check properties. Zero means CCC=0 and all checks Yes.17/// Bits 0..7: CCC; 8..9: NFC_QC; 10..11: NFKC_QC;18/// bit 12: NFD_QC; bit 13: NFKD_QC. Quick_Check: Yes=0, No=1, Maybe=2.19fn normalization_values(20  ccc : FixedArray[Int32],21  derived_properties : String,22) -> Array[Int32] raise {23  let values = Array::makei(ccc.length(), cp => ccc[cp])24  let seen = Array::make(4, false)25  // Properties can have separate No and Maybe sections, so track duplicates26  // per code point rather than requiring globally sorted ranges.27  let assigned = Array::make(@emitter.MaxCodePoint + 1, 0)28  for fields in @parsing.data_lines(derived_properties) {29    if fields.length() < 2 {30      continue31    }32    let (index, shift, mask) = match fields[1] {33      "NFC_QC" => (0, 8, 3)34      "NFKC_QC" => (1, 10, 3)35      "NFD_QC" => (2, 12, 1)36      "NFKD_QC" => (3, 13, 1)37      _ => continue38    }39    guard fields.length() == 3 else {40      fail("Quick_Check record must contain a range, property, and value")41    }42    let value = match fields[2] {43      "Y" => 044      "N" => 145      "M" if mask == 3 => 246      _ => fail("Invalid Quick_Check value")47    }48    let range = @parsing.parse_code_point_range(fields[0])49    guard range.start >= 0 &&50      range.start <= range.end &&51      range.end <= @emitter.MaxCodePoint else {52      fail("Invalid Quick_Check range")53    }54    seen[index] = true55    for cp in range.start..<=range.end {56      guard (assigned[cp] & (1 << index)) == 0 else {57        fail("Overlapping Quick_Check ranges")58      }59      assigned[cp] = assigned[cp] | (1 << index)60      values[cp] = values[cp] | (value << shift)61    }62  }63  guard seen.all(value => value) else { fail("Missing Quick_Check properties") }64  values65}6667///|68/// Emit a norm16 trie. Values below 0x8000 contain packed properties directly;69/// values with bit 15 set index six-byte records (properties, decomposition row70/// + 1, composition group + 1). Zero indices denote absent mappings/groups.71///72/// `exclusions` are the code points `CompositionExclusions.txt` lists, and73/// `derived_properties` is `DerivedNormalizationProps.txt`.74pub fn emit_normalization(75  data : UnicodeData,76  exclusions : Array[Int32],77  derived_properties : String,78) -> String raise {79  let compositions = build_composition_table(data, exclusions)80  let values = normalization_values(data.ccc, derived_properties)81  let decomp_indices = Array::make(@emitter.MaxCodePoint + 1, 0)82  for index, entry in data.decompositions {83    // `lookup_normalization_record` keeps the row + 1 in 15 bits.84    guard index < 32767 else {85      fail("Too many decomposition rows for a normalization record")86    }87    decomp_indices[entry.code_point] = index + 188  }89  let composition_groups = Array::make(@emitter.MaxCodePoint + 1, 0)90  let offsets = composition_group_offsets(compositions)91  for group in 0..<(offsets.length() - 1) {92    guard group < 65535 else { fail("Too many composition groups for norm16") }93    composition_groups[compositions[offsets[group]].first] = group + 194  }95  let extra : Array[Int32] = []96  for cp in 0..<=@emitter.MaxCodePoint {97    if decomp_indices[cp] != 0 || composition_groups[cp] != 0 {98      let record = extra.length() / 699      guard record < 32768 else { fail("Too many extra records for norm16") }100      for field in [values[cp], decomp_indices[cp], composition_groups[cp]] {101        extra.push(field & 255)102        extra.push(field >> 8)103      }104      values[cp] = 0x8000 | record105    }106  }107  let mut last = @emitter.MaxCodePoint108  while last > 0 && values[last] == 0 {109    last -= 1110  }111  let top_size = 1 << NormalizationTopShift112  let limit = Int32::max(113    NormalizationBmpLimit,114    (last + top_size) / top_size * top_size,115  )116  let bmp = @emitter.deduplicate_blocks(117    values[:NormalizationBmpLimit].to_owned(),118    1 << NormalizationBmpShift,119  )120  let bmp_offsets = bmp.ids.map(id => id << NormalizationBmpShift)121  let leaf = @emitter.deduplicate_blocks(122    values[NormalizationBmpLimit:limit].to_owned(),123    1 << NormalizationLeafShift,124  )125  let mid = @emitter.deduplicate_blocks(126    leaf.ids,127    1 << (NormalizationTopShift - NormalizationLeafShift),128  )129  guard mid.ids.all(id => id >= 0 && id < 256) else {130    fail("Normalization trie top indices exceed their encoded width")131  }132  let mid_shift = NormalizationTopShift - NormalizationLeafShift133  let mid_mask = (1 << mid_shift) - 1134  let leaf_mask = (1 << NormalizationLeafShift) - 1135  // Check the encoded representation, including the implicit default tail,136  // before emitting source. Validate every derived supplementary index before137  // its access: emitted unsafe_get calls rely on these immutable tables.138  for cp in 0..<=@emitter.MaxCodePoint {139    let actual = if cp < NormalizationBmpLimit {140      bmp.blocks[bmp_offsets[cp >> NormalizationBmpShift] +141      (cp & ((1 << NormalizationBmpShift) - 1))]142    } else if cp >= limit {143      0144    } else {145      let top_index = (cp - NormalizationBmpLimit) >> NormalizationTopShift146      guard top_index >= 0 && top_index < mid.ids.length() else {147        fail(148          "Normalization top index \{top_index} out of bounds at code point \{cp}",149        )150      }151      let mid_index = (mid.ids[top_index] << mid_shift) |152        ((cp >> NormalizationLeafShift) & mid_mask)153      guard mid_index >= 0 && mid_index < mid.blocks.length() else {154        fail(155          "Normalization mid index \{mid_index} out of bounds at code point \{cp}",156        )157      }158      let leaf_index = (mid.blocks[mid_index] << NormalizationLeafShift) |159        (cp & leaf_mask)160      guard leaf_index >= 0 && leaf_index < leaf.blocks.length() else {161        fail(162          "Normalization leaf index \{leaf_index} out of bounds at code point \{cp}",163        )164      }165      leaf.blocks[leaf_index]166    }167    guard actual == values[cp] else {168      fail("Normalization trie mismatch at code point \{cp}")169    }170  }171  let out = @emitter.Emitter::new()172  out.write_file_header(173    "Normalization descriptors", "UnicodeData.txt, CompositionExclusions.txt and DerivedNormalizationProps.txt",174  )175  // Int constants are emitted as compact static data on every backend.176  // UInt16 array literals currently expand to per-element initialization in Wasm-GC.177  out.write_int_array(178    "BMP block offsets (\{1 << NormalizationBmpShift} code points per block)",179    "normalization_bmp_index",180    bmp_offsets,181    hex=false,182  )183  out.write_int_array(184    "BMP norm16 values: direct properties or tagged extra-record indices",185    "normalization_bmp_data",186    bmp.blocks,187    hex=false,188  )189  out.write_byte_array(190    "Supplementary top-level block indices (\{top_size} code points per block)",191    "normalization_trie_top",192    mid.ids,193  )194  out.write_int_array(195    "Supplementary leaf block indices (\{1 << NormalizationLeafShift} code points per block)",196    "normalization_trie_mid",197    mid.blocks,198    hex=false,199  )200  out.write_int_array(201    "Supplementary norm16 values: direct properties or tagged extra-record indices",202    "normalization_trie_leaf",203    leaf.blocks,204    hex=false,205  )206  out.write_byte_array(207    "Six-byte records: packed properties, decomposition row + 1, composition group + 1 (all u16 LE)",208    "normalization_extra", extra,209  )210  out.write(211    (212      $|///|213      $|// Ordinary Wasm benefits from omitting the validated supplementary checks.214      $|// Keep the existing Native/JS shape; Wasm-GC array.get is bounds-checked.215      $|#cfg(target="wasm")216      $|const UncheckedSupplementaryLookup : Bool = true217      $|218      $|///|219      $|#cfg(not(target="wasm"))220      $|const UncheckedSupplementaryLookup : Bool = false221      $|222      $|///|223      $|/// Bit 15 tags an extra-record index; otherwise the value is packed properties.224      $|fn lookup_norm16(c : Char) -> Int {225      $|  let cp = c.to_int()226      $|  if cp < \{NormalizationBmpLimit} {227      $|    return lookup_bmp_norm16(cp)228      $|  }229      $|  lookup_supplementary_norm16(cp)230      $|}231      $|232      $|///|233      $|/// Two indexed loads for BMP normalization descriptors.234      $|fn lookup_bmp_norm16(cp : Int) -> Int {235      $|  normalization_bmp_data[normalization_bmp_index[cp >> \{NormalizationBmpShift}] + (cp & \{(1 << NormalizationBmpShift) - 1})]236      $|}237      $|238      $|///|239      $|/// Keep the compressed supplementary path out of the BMP lookup.240      $|fn lookup_supplementary_norm16(cp : Int) -> Int {241      $|  if cp >= \{limit} {242      $|    return 0243      $|  }244      $|  if UncheckedSupplementaryLookup {245      $|    // SAFETY: callers ensure cp >= \{NormalizationBmpLimit}; the guard above bounds cp.246      $|    // The generator validates all three indices for every cp in this range.247      $|    // These tables are immutable.248      $|    let mid = (normalization_trie_top.unsafe_get((cp - \{NormalizationBmpLimit}) >> \{NormalizationTopShift}).to_int() << \{mid_shift}) |249      $|      ((cp >> \{NormalizationLeafShift}) & \{mid_mask})250      $|    let leaf = normalization_trie_mid.unsafe_get(mid)251      $|    normalization_trie_leaf.unsafe_get((leaf << \{NormalizationLeafShift}) | (cp & \{leaf_mask}))252      $|  } else {253      $|    let mid = (normalization_trie_top[(cp - \{NormalizationBmpLimit}) >> \{NormalizationTopShift}].to_int() << \{mid_shift}) |254      $|      ((cp >> \{NormalizationLeafShift}) & \{mid_mask})255      $|    let leaf = normalization_trie_mid[mid]256      $|    normalization_trie_leaf[(leaf << \{NormalizationLeafShift}) | (cp & \{leaf_mask})]257      $|  }258      $|}259      $|260      $|///|261      $|/// Packed properties. Bits 0..7: CCC; 8..9: NFC_QC; 10..11: NFKC_QC;262      $|/// bit 12: NFD_QC; bit 13: NFKD_QC. Yes=0, No=1, Maybe=2 (NFC/NFKC).263      $|pub fn lookup_normalization_properties(c : Char) -> Int {264      $|  // Dispatch here so the full-scan property path has no extra lookup wrapper.265      $|  let cp = c.to_int()266      $|  let norm16 = if cp < \{NormalizationBmpLimit} {267      $|    lookup_bmp_norm16(cp)268      $|  } else {269      $|    lookup_supplementary_norm16(cp)270      $|  }271      $|  if norm16 < 0x8000 {272      $|    return norm16273      $|  }274      $|  let offset = (norm16 & 0x7FFF) * 6275      $|  // SAFETY: every norm16 from 0x8000 indexes one of the six-byte extra276      $|  // records the generator writes. The view has exactly 2 bytes, so277      $|  // the pattern always matches, and they are read in one load.278      $|  guard normalization_extra.unsafe_view(start=offset, end=offset + 2)279      $|    is [u16le(properties)] else {280      $|    abort("unreachable")281      $|  }282      $|  properties.reinterpret_as_int()283      $|}284      $|285      $|///|286      $|/// Packed properties as `lookup_normalization_properties` gives them in287      $|/// bits 0..15, and the decomposition row + 1 in bits 16..30 (0 without288      $|/// a decomposition), from one lookup.289      $|pub fn lookup_normalization_record(c : Char) -> Int {290      $|  let cp = c.to_int()291      $|  let norm16 = if cp < \{NormalizationBmpLimit} {292      $|    lookup_bmp_norm16(cp)293      $|  } else {294      $|    lookup_supplementary_norm16(cp)295      $|  }296      $|  if norm16 < 0x8000 {297      $|    return norm16298      $|  }299      $|  let offset = (norm16 & 0x7FFF) * 6300      $|  // SAFETY: every norm16 from 0x8000 indexes one of the six-byte extra301      $|  // records the generator writes. The view has exactly 4 bytes, so302      $|  // the pattern always matches, and they are read in one load.303      $|  guard normalization_extra.unsafe_view(start=offset, end=offset + 4)304      $|    is [i32le(record)] else {305      $|    abort("unreachable")306      $|  }307      $|  record308      $|}309      $|310      $|///|311      $|pub fn normalization_composition_group(c : Char) -> Int {312      $|  let norm16 = lookup_norm16(c)313      $|  if norm16 < 0x8000 { return -1 }314      $|  let offset = (norm16 & 0x7FFF) * 6 + 4315      $|  (normalization_extra[offset].to_int() |316      $|    (normalization_extra[offset + 1].to_int() << 8)) - 1317      $|}318      $|319    ),320  )321  out.finish()322}323