tools/ucd/case_mapping.mbt1///|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
///|
/// The trie covers planes 0-1, which hold every case mapping.
const CaseTrieLimit : Int32 = 0x20000
///|
/// Each top-level trie entry covers `1 << CaseTrieTopShift` code points.
const CaseTrieTopShift : Int32 = 8
///|
/// Each leaf block holds `1 << CaseTrieLeafShift` record indices.
const CaseTrieLeafShift : Int32 = 4
///|
/// One case conversion: its simple mappings as per-code-point deltas, and
/// the full mappings that differ from the simple one.
priv struct CaseTable {
/// "upper", "lower" or "title": the prefix of generated table names.
name : String
/// `target - code_point` of the simple mapping, 0 where there is none.
deltas : Array[Int32]
/// Full mappings other than the single simple target, by code point.
special : Map[Int32, Array[Int32]]
}
///|
fn CaseTable::new(
name : String,
simple : Array[SimpleMappingEntry],
special_casing : Array[FullMappingEntry],
) -> CaseTable raise {
let deltas = Array::make(CaseTrieLimit, 0)
for entry in simple {
guard entry.code_point < CaseTrieLimit else {
fail(
"Case mapping at or above \{@emitter.hex_literal(CaseTrieLimit)} needs trie coverage",
)
}
deltas[entry.code_point] = entry.target - entry.code_point
}
let special : Map[Int32, Array[Int32]] = Map([])
for entry in special_casing {
guard entry.code_point < CaseTrieLimit else {
fail(
"Case mapping at or above \{@emitter.hex_literal(CaseTrieLimit)} needs trie coverage",
)
}
// A full mapping overrides the simple one. When they agree, the simple
// delta already describes it.
let simple_target = entry.code_point + deltas[entry.code_point]
if entry.targets == [simple_target] {
special.remove(entry.code_point)
} else {
special[entry.code_point] = entry.targets
}
}
{ name, deltas, special, }
}
///|
/// Emit case mapping data as a three-level trie from code points to shared
/// records, plus the few full mappings that are not a single character.
///
/// A record holds the simple uppercase, lowercase and titlecase deltas of a
/// code point and one flag per case telling whether the code point also has
/// a special full mapping. Most cased characters share a record, so record
/// indices fit in one byte and identical trie blocks are shared.
pub fn emit_case_mapping(
data : UnicodeData,
special_casing : SpecialCasingData,
) -> String raise {
let cases = [
CaseTable::new("upper", data.simple_uppercase, special_casing.upper_mapping),
CaseTable::new("lower", data.simple_lowercase, special_casing.lower_mapping),
CaseTable::new("title", data.simple_titlecase, special_casing.title_mapping),
]
// A record is one delta per case followed by the special-mapping flags.
// Record 0 is a code point without any case mapping.
let record_ids : Map[Array[Int32], Int32] = Map([([0, 0, 0, 0], 0)])
let records : Array[Array[Int32]] = [[0, 0, 0, 0]]
let values = Array::make(CaseTrieLimit, 0)
for code_point in 0..<CaseTrieLimit {
let record = cases.map(table => table.deltas[code_point])
let mut flags = 0
for bit, table in cases {
if table.special.contains(code_point) {
flags = flags | (1 << bit)
}
}
record.push(flags)
values[code_point] = match record_ids.get(record) {
Some(id) => id
None => {
let id = records.length()
record_ids[record] = id
records.push(record)
id
}
}
}
guard records.length() <= 0x100 else {
fail("Case mapping has too many distinct records for one byte")
}
// Leaf level: blocks of record indices.
let leaf = @emitter.deduplicate_blocks(values, 1 << CaseTrieLeafShift)
// Mid level: blocks of leaf block indices; `mid.ids` is the top level.
let mid = @emitter.deduplicate_blocks(
leaf.ids,
1 << (CaseTrieTopShift - CaseTrieLeafShift),
)
guard mid.ids.all(id => id < 0x100) else {
fail("Case mapping trie has too many mid blocks for one byte")
}
guard mid.blocks.all(id => id < 0x100) else {
fail("Case mapping trie has too many leaf blocks for one byte")
}
let mid_mask = (1 << (CaseTrieTopShift - CaseTrieLeafShift)) - 1
let leaf_mask = (1 << CaseTrieLeafShift) - 1
let out = @emitter.Emitter::new()
out.write_file_header(
"Case mapping lookup data", "UnicodeData.txt and SpecialCasing.txt",
)
out.write_byte_array(
"Case mapping trie top level: `cp >> \{CaseTrieTopShift}` to mid block index",
"case_trie_top",
mid.ids,
)
out.write_byte_array(
"Case mapping trie mid level: leaf block indices",
"case_trie_mid",
mid.blocks,
)
out.write_byte_array(
"Case mapping trie leaf level: record indices in blocks of \{1 << CaseTrieLeafShift}",
"case_trie_leaf",
leaf.blocks,
)
for index, table in cases {
out.write_int_array(
"Simple \{table.name}case mapping of each record as `target - code point`",
"case_\{table.name}_deltas",
records.map(record => record[index]),
hex=false,
)
}
out.write_byte_array(
"Special full mappings of each record: bit 0 upper, bit 1 lower, bit 2 title",
"case_special_flags",
records.map(record => record[cases.length()]),
)
for table in cases {
let code_points = table.special.keys().collect()
code_points.sort()
out.write_int_array(
"Code points whose full \{table.name}case mapping is not their simple one (sorted for binary search)",
"special_\{table.name}_cps",
code_points,
hex=true,
)
out.write_string_array(
"Full \{table.name}case mapping of each such code point",
"special_\{table.name}_strings",
code_points.map(code_point => table.special[code_point]),
)
}
out.write_string_array(
"One-character strings of the ASCII characters, so that mapping to one allocates nothing",
"ascii_strings",
Array::makei(0x80, code_point => [code_point]),
)
out.write(
(
$|///|
$|/// Index of the record holding a character's case mappings
$|fn lookup_case_record(c : Char) -> Int {
$| let cp = c.to_int()
$| if cp >= \{@emitter.hex_literal(CaseTrieLimit)} {
$| return 0
$| }
$| let mid = (case_trie_top[cp >> \{CaseTrieTopShift}].to_int() << \{CaseTrieTopShift - CaseTrieLeafShift}) |
$| ((cp >> \{CaseTrieLeafShift}) & \{mid_mask})
$| let leaf = case_trie_mid[mid].to_int()
$| case_trie_leaf[(leaf << \{CaseTrieLeafShift}) | (cp & \{leaf_mask})].to_int()
$|}
$|
),
)
for bit, table in cases {
let name = table.name
let flag = 1 << bit
out.write(
(
$|///|
$|/// Look up simple \{name}case mapping for a character
$|/// Returns the character itself if no mapping exists
$|pub fn lookup_simple_\{name}case(c : Char) -> Char {
$| (c.to_int() + case_\{name}_deltas[lookup_case_record(c)]).unsafe_to_char()
$|}
$|
$|///|
$|/// Full \{name}case mapping of a character as a string
$|/// Returns the character itself if no mapping exists
$|pub fn full_\{name}case(c : Char) -> String {
$| let record = lookup_case_record(c)
$| if (case_special_flags[record].to_int() & \{flag}) != 0 {
$| let index = find_special_\{name}(c.to_int())
$| if index >= 0 {
$| return special_\{name}_strings[index]
$| }
$| }
$| let target = c.to_int() + case_\{name}_deltas[record]
$| if target < 0x80 {
$| ascii_strings[target]
$| } else {
$| target.unsafe_to_char().to_string()
$| }
$|}
$|
$|///|
$|/// Look up full \{name}case mapping for a character
$|/// Returns Some(array of chars) if a mapping exists, None otherwise
$|pub fn lookup_full_\{name}case(c : Char) -> Array[Char]? {
$| let record = lookup_case_record(c)
$| if (case_special_flags[record].to_int() & \{flag}) != 0 {
$| let index = find_special_\{name}(c.to_int())
$| if index >= 0 {
$| return Some(special_\{name}_strings[index].to_array())
$| }
$| }
$| let delta = case_\{name}_deltas[record]
$| if delta == 0 {
$| None
$| } else {
$| Some([(c.to_int() + delta).unsafe_to_char()])
$| }
$|}
$|
),
)
out.write_sorted_search(
name="find_special_\{name}",
values="special_\{name}_cps",
)
}
out.finish()
}