tools/ucd/case_folding.mbt1///|2priv struct FoldMapping {3 start : Int324 end : Int325 targets : Array[Int32]6}78///|9fn parse_fold_mappings(10 content : String,11 nfkc~ : Bool,12) -> Array[FoldMapping] raise {13 let entries : Array[FoldMapping] = []14 let mut previous_end = -115 for record in @parsing.data_lines(content) {16 guard record is [range, status, .. fields] else {17 fail("Invalid folding record: \{record[0]}")18 }19 if nfkc {20 if status != "NFKC_CF" {21 continue22 }23 } else if status != "C" && status != "F" {24 // S is simple folding; T is Turkic tailoring, neither is default full folding.25 continue26 }27 guard fields is [mapping, ..] else {28 fail("Missing folding target: \{range}")29 }30 let range = @parsing.parse_code_point_range(range)31 guard range.start > previous_end &&32 range.start <= range.end &&33 range.end <= 0x10FFFF else {34 fail("Folding ranges must be valid, sorted and non-overlapping")35 }36 let targets = @parsing.parse_code_point_sequence(mapping)37 guard targets.all(cp => {38 cp >= 0 && cp <= 0x10FFFF && !(cp >= 0xD800 && cp <= 0xDFFF)39 }) else {40 fail("Invalid folding target")41 }42 if !nfkc && (range.start != range.end || targets.is_empty()) {43 fail("Invalid full case folding mapping")44 }45 entries.push({ start: range.start, end: range.end, targets, })46 previous_end = range.end47 }48 guard !entries.is_empty() else { fail("Missing folding mappings") }49 entries50}5152///|53/// Number of distinct deltas a folding trie can encode: its values fit in a54/// byte, and kinds 0 and 1 are taken.55const FoldDeltaLimit : Int32 = 2545657///|58/// Emit folding data in two parts.59///60/// `<prefix>_kind` is a byte-valued trie giving every code point a kind:61/// 0 when the code point folds to itself, 1 when its mapping must be looked up62/// with `lookup_<prefix>`, and from 2 on an index into `<prefix>_deltas`, for63/// a mapping to the single code point `cp + <prefix>_deltas[kind]`. The most64/// frequent deltas get a kind, so nearly every cased letter is folded without65/// a search.66///67/// `lookup_<prefix>` searches the entries holding a code point of kind 1:68/// sorted range starts (plus range ends when some range covers more than one69/// code point), with all targets packed into one string and sliced by 16-bit70/// offsets. One string instead of a string per mapping keeps the table free of71/// pointers and per-literal headers.72fn emit_fold_mappings(73 entries : Array[FoldMapping],74 prefix : String,75 source : String,76) -> String raise {77 let counts : Map[Int32, Int32] = Map([])78 for entry in entries {79 if entry.targets is [target] {80 for cp in entry.start..<=entry.end {81 counts.set(target - cp, counts.get(target - cp).unwrap_or(0) + 1)82 }83 }84 }85 // Most frequent first; equal counts by delta, so the output is stable.86 let ranked = counts.to_array()87 ranked.sort_by((a, b) => {88 if a.1 != b.1 {89 b.1.compare(a.1)90 } else {91 a.0.compare(b.0)92 }93 })94 let deltas = [0, 0]95 let kinds : Map[Int32, Int32] = Map([])96 for pair in ranked[:FoldDeltaLimit] {97 kinds.set(pair.0, deltas.length())98 deltas.push(pair.0)99 }100 let values = FixedArray::make(@emitter.MaxCodePoint + 1, 0)101 let searched = []102 for entry in entries {103 let mut found = false104 for cp in entry.start..<=entry.end {105 let kind = if entry.targets is [target] {106 kinds.get(target - cp).unwrap_or(1)107 } else {108 1109 }110 values[cp] = kind111 found = found || kind == 1112 }113 if found {114 searched.push(entry)115 }116 }117 // The folding code maps ASCII without the tables, A-Z to a-z only.118 for cp in 0..<0x80 {119 let delta = if cp >= 'A' && cp <= 'Z' { 32 } else { 0 }120 guard values[cp] != 1 && deltas[values[cp]] == delta else {121 fail(122 "\{prefix} folds ASCII \{@emitter.hex_literal(cp)} other than A-Z to a-z",123 )124 }125 }126 let has_ranges = searched.any(e => e.start != e.end)127 let text : Array[Int32] = []128 let offsets = [0]129 let mut units = 0130 for entry in searched {131 for target in entry.targets {132 text.push(target)133 units += if target > 0xFFFF { 2 } else { 1 }134 }135 offsets.push(units)136 }137 let out = @emitter.Emitter::new()138 out.write_file_header("\{prefix} mapping data", source)139 out.write_value_trie(140 property="\{prefix} kind",141 prefix="\{prefix}_kind",142 lookup="fn \{prefix}_kind",143 lookup_doc=[144 "How `c` folds: 0 to itself, 1 to the mapping `lookup_\{prefix}` finds,",145 "and from 2 on to the code point `c + \{prefix}_deltas[kind]`.",146 ],147 value_bits=8,148 values,149 )150 out.write_int_array(151 "Code point deltas by kind; kinds 0 and 1 have none",152 "\{prefix}_deltas",153 deltas,154 hex=false,155 )156 out.write_int_array(157 if has_ranges {158 "Sorted inclusive range starts of the entries with a code point of kind 1"159 } else {160 "Sorted code points of kind 1"161 },162 "\{prefix}_starts",163 searched.map(e => e.start),164 hex=true,165 )166 if has_ranges {167 out.write_int_array(168 "Inclusive range ends",169 "\{prefix}_ends",170 searched.map(e => e.end),171 hex=true,172 )173 }174 out.write_uint16_array(175 "UTF-16 offsets into `\{prefix}_text`: entry `i` maps to `[offsets[i], offsets[i + 1])`",176 "\{prefix}_offsets",177 offsets,178 )179 out.write("///|\n/// Targets of all entries, concatenated\n")180 out.write(181 "let \{prefix}_text : String = \{@emitter.string_literal(text)}\n\n",182 )183 let (found_test, found_doc) = if has_ranges {184 (185 (186 $| } else if cp > \{prefix}_ends[mid] {187 ),188 "the range holding `c`",189 )190 } else {191 (192 (193 $| } else if cp > \{prefix}_starts[mid] {194 ),195 "`c`",196 )197 }198 out.write(199 (200 $|///|201 $|/// The mapping of \{found_doc}, as a view of `\{prefix}_text`, for202 $|/// a code point of kind 1. None means identity; an empty view means203 $|/// removal.204 $|fn lookup_\{prefix}(c : Char) -> StringView? {205 $| let cp = c.to_int()206 $| let mut low = 0207 $| let mut high = \{prefix}_starts.length()208 $| while low < high {209 $| let mid = (low + high) / 2210 $| if cp < \{prefix}_starts[mid] {211 $| high = mid212 $|\{found_test}213 $| low = mid + 1214 $| } else {215 $| return Some(216 $| \{prefix}_text.unsafe_view(217 $| start=\{prefix}_offsets[mid].to_int(),218 $| end=\{prefix}_offsets[mid + 1].to_int(),219 $| ),220 $| )221 $| }222 $| }223 $| None224 $|}225 $|226 ),227 )228 out.finish()229}230231///|232pub fn emit_case_folding(content : String) -> String raise {233 emit_fold_mappings(234 parse_fold_mappings(content, nfkc=false),235 "case_folding",236 "CaseFolding.txt (C and F mappings)",237 )238}239240///|241pub fn emit_nfkc_casefold(content : String) -> String raise {242 emit_fold_mappings(243 parse_fold_mappings(content, nfkc=true),244 "nfkc_casefold",245 "DerivedNormalizationProps.txt (NFKC_CF)",246 )247}248
///|
priv struct FoldMapping {
start : Int32
end : Int32
targets : Array[Int32]
}
///|
fn parse_fold_mappings(
content : String,
nfkc~ : Bool,
) -> Array[FoldMapping] raise {
let entries : Array[FoldMapping] = []
let mut previous_end = -1
for record in @parsing.data_lines(content) {
guard record is [range, status, .. fields] else {
fail("Invalid folding record: \{record[0]}")
}
if nfkc {
if status != "NFKC_CF" {
continue
}
} else if status != "C" && status != "F" {
// S is simple folding; T is Turkic tailoring, neither is default full folding.
continue
}
guard fields is [mapping, ..] else {
fail("Missing folding target: \{range}")
}
let range = @parsing.parse_code_point_range(range)
guard range.start > previous_end &&
range.start <= range.end &&
range.end <= 0x10FFFF else {
fail("Folding ranges must be valid, sorted and non-overlapping")
}
let targets = @parsing.parse_code_point_sequence(mapping)
guard targets.all(cp => {
cp >= 0 && cp <= 0x10FFFF && !(cp >= 0xD800 && cp <= 0xDFFF)
}) else {
fail("Invalid folding target")
}
if !nfkc && (range.start != range.end || targets.is_empty()) {
fail("Invalid full case folding mapping")
}
entries.push({ start: range.start, end: range.end, targets, })
previous_end = range.end
}
guard !entries.is_empty() else { fail("Missing folding mappings") }
entries
}
///|
/// Number of distinct deltas a folding trie can encode: its values fit in a
/// byte, and kinds 0 and 1 are taken.
const FoldDeltaLimit : Int32 = 254
///|
/// Emit folding data in two parts.
///
/// `<prefix>_kind` is a byte-valued trie giving every code point a kind:
/// 0 when the code point folds to itself, 1 when its mapping must be looked up
/// with `lookup_<prefix>`, and from 2 on an index into `<prefix>_deltas`, for
/// a mapping to the single code point `cp + <prefix>_deltas[kind]`. The most
/// frequent deltas get a kind, so nearly every cased letter is folded without
/// a search.
///
/// `lookup_<prefix>` searches the entries holding a code point of kind 1:
/// sorted range starts (plus range ends when some range covers more than one
/// code point), with all targets packed into one string and sliced by 16-bit
/// offsets. One string instead of a string per mapping keeps the table free of
/// pointers and per-literal headers.
fn emit_fold_mappings(
entries : Array[FoldMapping],
prefix : String,
source : String,
) -> String raise {
let counts : Map[Int32, Int32] = Map([])
for entry in entries {
if entry.targets is [target] {
for cp in entry.start..<=entry.end {
counts.set(target - cp, counts.get(target - cp).unwrap_or(0) + 1)
}
}
}
// Most frequent first; equal counts by delta, so the output is stable.
let ranked = counts.to_array()
ranked.sort_by((a, b) => {
if a.1 != b.1 {
b.1.compare(a.1)
} else {
a.0.compare(b.0)
}
})
let deltas = [0, 0]
let kinds : Map[Int32, Int32] = Map([])
for pair in ranked[:FoldDeltaLimit] {
kinds.set(pair.0, deltas.length())
deltas.push(pair.0)
}
let values = FixedArray::make(@emitter.MaxCodePoint + 1, 0)
let searched = []
for entry in entries {
let mut found = false
for cp in entry.start..<=entry.end {
let kind = if entry.targets is [target] {
kinds.get(target - cp).unwrap_or(1)
} else {
1
}
values[cp] = kind
found = found || kind == 1
}
if found {
searched.push(entry)
}
}
// The folding code maps ASCII without the tables, A-Z to a-z only.
for cp in 0..<0x80 {
let delta = if cp >= 'A' && cp <= 'Z' { 32 } else { 0 }
guard values[cp] != 1 && deltas[values[cp]] == delta else {
fail(
"\{prefix} folds ASCII \{@emitter.hex_literal(cp)} other than A-Z to a-z",
)
}
}
let has_ranges = searched.any(e => e.start != e.end)
let text : Array[Int32] = []
let offsets = [0]
let mut units = 0
for entry in searched {
for target in entry.targets {
text.push(target)
units += if target > 0xFFFF { 2 } else { 1 }
}
offsets.push(units)
}
let out = @emitter.Emitter::new()
out.write_file_header("\{prefix} mapping data", source)
out.write_value_trie(
property="\{prefix} kind",
prefix="\{prefix}_kind",
lookup="fn \{prefix}_kind",
lookup_doc=[
"How `c` folds: 0 to itself, 1 to the mapping `lookup_\{prefix}` finds,",
"and from 2 on to the code point `c + \{prefix}_deltas[kind]`.",
],
value_bits=8,
values,
)
out.write_int_array(
"Code point deltas by kind; kinds 0 and 1 have none",
"\{prefix}_deltas",
deltas,
hex=false,
)
out.write_int_array(
if has_ranges {
"Sorted inclusive range starts of the entries with a code point of kind 1"
} else {
"Sorted code points of kind 1"
},
"\{prefix}_starts",
searched.map(e => e.start),
hex=true,
)
if has_ranges {
out.write_int_array(
"Inclusive range ends",
"\{prefix}_ends",
searched.map(e => e.end),
hex=true,
)
}
out.write_uint16_array(
"UTF-16 offsets into `\{prefix}_text`: entry `i` maps to `[offsets[i], offsets[i + 1])`",
"\{prefix}_offsets",
offsets,
)
out.write("///|\n/// Targets of all entries, concatenated\n")
out.write(
"let \{prefix}_text : String = \{@emitter.string_literal(text)}\n\n",
)
let (found_test, found_doc) = if has_ranges {
(
(
$| } else if cp > \{prefix}_ends[mid] {
),
"the range holding `c`",
)
} else {
(
(
$| } else if cp > \{prefix}_starts[mid] {
),
"`c`",
)
}
out.write(
(
$|///|
$|/// The mapping of \{found_doc}, as a view of `\{prefix}_text`, for
$|/// a code point of kind 1. None means identity; an empty view means
$|/// removal.
$|fn lookup_\{prefix}(c : Char) -> StringView? {
$| let cp = c.to_int()
$| let mut low = 0
$| let mut high = \{prefix}_starts.length()
$| while low < high {
$| let mid = (low + high) / 2
$| if cp < \{prefix}_starts[mid] {
$| high = mid
$|\{found_test}
$| low = mid + 1
$| } else {
$| return Some(
$| \{prefix}_text.unsafe_view(
$| start=\{prefix}_offsets[mid].to_int(),
$| end=\{prefix}_offsets[mid + 1].to_int(),
$| ),
$| )
$| }
$| }
$| None
$|}
$|
),
)
out.finish()
}
///|
pub fn emit_case_folding(content : String) -> String raise {
emit_fold_mappings(
parse_fold_mappings(content, nfkc=false),
"case_folding",
"CaseFolding.txt (C and F mappings)",
)
}
///|
pub fn emit_nfkc_casefold(content : String) -> String raise {
emit_fold_mappings(
parse_fold_mappings(content, nfkc=true),
"nfkc_casefold",
"DerivedNormalizationProps.txt (NFKC_CF)",
)
}