unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

tools/ucd/case_mapping.mbt
1///|2/// The trie covers planes 0-1, which hold every case mapping.3const CaseTrieLimit : Int32 = 0x2000045///|6/// Each top-level trie entry covers `1 << CaseTrieTopShift` code points.7const CaseTrieTopShift : Int32 = 889///|10/// Each leaf block holds `1 << CaseTrieLeafShift` record indices.11const CaseTrieLeafShift : Int32 = 41213///|14/// One case conversion: its simple mappings as per-code-point deltas, and15/// the full mappings that differ from the simple one.16priv struct CaseTable {17  /// "upper", "lower" or "title": the prefix of generated table names.18  name : String19  /// `target - code_point` of the simple mapping, 0 where there is none.20  deltas : Array[Int32]21  /// Full mappings other than the single simple target, by code point.22  special : Map[Int32, Array[Int32]]23}2425///|26fn CaseTable::new(27  name : String,28  simple : Array[SimpleMappingEntry],29  special_casing : Array[FullMappingEntry],30) -> CaseTable raise {31  let deltas = Array::make(CaseTrieLimit, 0)32  for entry in simple {33    guard entry.code_point < CaseTrieLimit else {34      fail(35        "Case mapping at or above \{@emitter.hex_literal(CaseTrieLimit)} needs trie coverage",36      )37    }38    deltas[entry.code_point] = entry.target - entry.code_point39  }40  let special : Map[Int32, Array[Int32]] = Map([])41  for entry in special_casing {42    guard entry.code_point < CaseTrieLimit else {43      fail(44        "Case mapping at or above \{@emitter.hex_literal(CaseTrieLimit)} needs trie coverage",45      )46    }47    // A full mapping overrides the simple one. When they agree, the simple48    // delta already describes it.49    let simple_target = entry.code_point + deltas[entry.code_point]50    if entry.targets == [simple_target] {51      special.remove(entry.code_point)52    } else {53      special[entry.code_point] = entry.targets54    }55  }56  { name, deltas, special, }57}5859///|60/// Emit case mapping data as a three-level trie from code points to shared61/// records, plus the few full mappings that are not a single character.62///63/// A record holds the simple uppercase, lowercase and titlecase deltas of a64/// code point and one flag per case telling whether the code point also has65/// a special full mapping. Most cased characters share a record, so record66/// indices fit in one byte and identical trie blocks are shared.67pub fn emit_case_mapping(68  data : UnicodeData,69  special_casing : SpecialCasingData,70) -> String raise {71  let cases = [72    CaseTable::new("upper", data.simple_uppercase, special_casing.upper_mapping),73    CaseTable::new("lower", data.simple_lowercase, special_casing.lower_mapping),74    CaseTable::new("title", data.simple_titlecase, special_casing.title_mapping),75  ]76  // A record is one delta per case followed by the special-mapping flags.77  // Record 0 is a code point without any case mapping.78  let record_ids : Map[Array[Int32], Int32] = Map([([0, 0, 0, 0], 0)])79  let records : Array[Array[Int32]] = [[0, 0, 0, 0]]80  let values = Array::make(CaseTrieLimit, 0)81  for code_point in 0..<CaseTrieLimit {82    let record = cases.map(table => table.deltas[code_point])83    let mut flags = 084    for bit, table in cases {85      if table.special.contains(code_point) {86        flags = flags | (1 << bit)87      }88    }89    record.push(flags)90    values[code_point] = match record_ids.get(record) {91      Some(id) => id92      None => {93        let id = records.length()94        record_ids[record] = id95        records.push(record)96        id97      }98    }99  }100  guard records.length() <= 0x100 else {101    fail("Case mapping has too many distinct records for one byte")102  }103  // Leaf level: blocks of record indices.104  let leaf = @emitter.deduplicate_blocks(values, 1 << CaseTrieLeafShift)105  // Mid level: blocks of leaf block indices; `mid.ids` is the top level.106  let mid = @emitter.deduplicate_blocks(107    leaf.ids,108    1 << (CaseTrieTopShift - CaseTrieLeafShift),109  )110  guard mid.ids.all(id => id < 0x100) else {111    fail("Case mapping trie has too many mid blocks for one byte")112  }113  guard mid.blocks.all(id => id < 0x100) else {114    fail("Case mapping trie has too many leaf blocks for one byte")115  }116  let mid_mask = (1 << (CaseTrieTopShift - CaseTrieLeafShift)) - 1117  let leaf_mask = (1 << CaseTrieLeafShift) - 1118  let out = @emitter.Emitter::new()119  out.write_file_header(120    "Case mapping lookup data", "UnicodeData.txt and SpecialCasing.txt",121  )122  out.write_byte_array(123    "Case mapping trie top level: `cp >> \{CaseTrieTopShift}` to mid block index",124    "case_trie_top",125    mid.ids,126  )127  out.write_byte_array(128    "Case mapping trie mid level: leaf block indices",129    "case_trie_mid",130    mid.blocks,131  )132  out.write_byte_array(133    "Case mapping trie leaf level: record indices in blocks of \{1 << CaseTrieLeafShift}",134    "case_trie_leaf",135    leaf.blocks,136  )137  for index, table in cases {138    out.write_int_array(139      "Simple \{table.name}case mapping of each record as `target - code point`",140      "case_\{table.name}_deltas",141      records.map(record => record[index]),142      hex=false,143    )144  }145  out.write_byte_array(146    "Special full mappings of each record: bit 0 upper, bit 1 lower, bit 2 title",147    "case_special_flags",148    records.map(record => record[cases.length()]),149  )150  for table in cases {151    let code_points = table.special.keys().collect()152    code_points.sort()153    out.write_int_array(154      "Code points whose full \{table.name}case mapping is not their simple one (sorted for binary search)",155      "special_\{table.name}_cps",156      code_points,157      hex=true,158    )159    out.write_string_array(160      "Full \{table.name}case mapping of each such code point",161      "special_\{table.name}_strings",162      code_points.map(code_point => table.special[code_point]),163    )164  }165  out.write_string_array(166    "One-character strings of the ASCII characters, so that mapping to one allocates nothing",167    "ascii_strings",168    Array::makei(0x80, code_point => [code_point]),169  )170  out.write(171    (172      $|///|173      $|/// Index of the record holding a character's case mappings174      $|fn lookup_case_record(c : Char) -> Int {175      $|  let cp = c.to_int()176      $|  if cp >= \{@emitter.hex_literal(CaseTrieLimit)} {177      $|    return 0178      $|  }179      $|  let mid = (case_trie_top[cp >> \{CaseTrieTopShift}].to_int() << \{CaseTrieTopShift - CaseTrieLeafShift}) |180      $|    ((cp >> \{CaseTrieLeafShift}) & \{mid_mask})181      $|  let leaf = case_trie_mid[mid].to_int()182      $|  case_trie_leaf[(leaf << \{CaseTrieLeafShift}) | (cp & \{leaf_mask})].to_int()183      $|}184      $|185    ),186  )187  for bit, table in cases {188    let name = table.name189    let flag = 1 << bit190    out.write(191      (192        $|///|193        $|/// Look up simple \{name}case mapping for a character194        $|/// Returns the character itself if no mapping exists195        $|pub fn lookup_simple_\{name}case(c : Char) -> Char {196        $|  (c.to_int() + case_\{name}_deltas[lookup_case_record(c)]).unsafe_to_char()197        $|}198        $|199        $|///|200        $|/// Full \{name}case mapping of a character as a string201        $|/// Returns the character itself if no mapping exists202        $|pub fn full_\{name}case(c : Char) -> String {203        $|  let record = lookup_case_record(c)204        $|  if (case_special_flags[record].to_int() & \{flag}) != 0 {205        $|    let index = find_special_\{name}(c.to_int())206        $|    if index >= 0 {207        $|      return special_\{name}_strings[index]208        $|    }209        $|  }210        $|  let target = c.to_int() + case_\{name}_deltas[record]211        $|  if target < 0x80 {212        $|    ascii_strings[target]213        $|  } else {214        $|    target.unsafe_to_char().to_string()215        $|  }216        $|}217        $|218        $|///|219        $|/// Look up full \{name}case mapping for a character220        $|/// Returns Some(array of chars) if a mapping exists, None otherwise221        $|pub fn lookup_full_\{name}case(c : Char) -> Array[Char]? {222        $|  let record = lookup_case_record(c)223        $|  if (case_special_flags[record].to_int() & \{flag}) != 0 {224        $|    let index = find_special_\{name}(c.to_int())225        $|    if index >= 0 {226        $|      return Some(special_\{name}_strings[index].to_array())227        $|    }228        $|  }229        $|  let delta = case_\{name}_deltas[record]230        $|  if delta == 0 {231        $|    None232        $|  } else {233        $|    Some([(c.to_int() + delta).unsafe_to_char()])234        $|  }235        $|}236        $|237      ),238    )239    out.write_sorted_search(240      name="find_special_\{name}",241      values="special_\{name}_cps",242    )243  }244  out.finish()245}246