tools/ucd/binary_property.mbt1///|2/// Binary property tries cover planes 0-3, like the General_Category trie.3/// The few ranges above are checked with explicit comparisons instead.4const BinaryTrieLimit : Int32 = 0x4000056///|7/// Each top-level trie entry covers `1 << BinaryTrieTopShift` code points.8const BinaryTrieTopShift : Int32 = 10910///|11/// Each leaf block is a bitset of `1 << BinaryTrieLeafShift` code points.12const BinaryTrieLeafShift : Int32 = 71314///|15/// Write a binary property as a three-level bitset trie for planes 0-316/// named `<prefix>_trie_top`, `<prefix>_trie_mid`, and `<prefix>_trie_leaf`,17/// followed by the lookup function `is_<prefix>`, where `<prefix>` is the18/// property name in lowercase (`White_Space` becomes `white_space`).19///20/// A set of code points that is not a Unicode property passes `lookup`, the21/// name of the lookup function, and `lookup_doc`, its one-line description.22/// Set `exported=false` for a lookup used only inside its generated package.23///24/// The top level maps `cp >> 10` to a mid block, the mid level maps the next25/// three bits to a leaf block, and each leaf block holds one bit per code26/// point for 128 code points. Identical blocks are shared at both levels.27fn write_binary_property_trie(28 out : @emitter.Emitter,29 property~ : String,30 lookup? : String,31 lookup_doc? : String,32 exported~ : Bool = true,33 ranges : Array[@parsing.CodePointRange],34) -> Unit raise {35 let prefix = property.to_lower()36 let visibility = if exported { "pub " } else { "" }37 let lookup = lookup.unwrap_or("is_\{prefix}")38 let lookup_doc = lookup_doc.unwrap_or(39 "Check whether a character has the Unicode \{property} property",40 )41 let bits = Array::make(BinaryTrieLimit / 8, 0)42 let high_ranges : Array[@parsing.CodePointRange] = []43 for range in ranges {44 for cp in range.start..<=Int32::min(range.end, BinaryTrieLimit - 1) {45 bits[cp >> 3] = bits[cp >> 3] | (1 << (cp & 7))46 }47 if range.end >= BinaryTrieLimit {48 high_ranges.push({49 start: Int32::max(range.start, BinaryTrieLimit),50 end: range.end,51 })52 }53 }54 // Leaf level: bitset blocks; `leaf.ids` has one entry per leaf block.55 let leaf = @emitter.deduplicate_blocks(bits, 1 << (BinaryTrieLeafShift - 3))56 // Mid level: blocks of leaf block indices; `mid.ids` is the top level.57 let mid = @emitter.deduplicate_blocks(58 leaf.ids,59 1 << (BinaryTrieTopShift - BinaryTrieLeafShift),60 )61 guard mid.ids.all(id => id < 0x100) else {62 fail("\{property} trie has too many mid blocks for one byte")63 }64 guard mid.blocks.all(id => id < 0x100) else {65 fail("\{property} trie has too many leaf blocks for one byte")66 }67 let high_check = if high_ranges.is_empty() {68 "false"69 } else {70 high_ranges71 .map(range => {72 "(cp >= \{@emitter.hex_literal(range.start)} && cp <= \{@emitter.hex_literal(range.end)})"73 })74 .join(" || ")75 }76 let mid_mask = (1 << (BinaryTrieTopShift - BinaryTrieLeafShift)) - 177 let byte_mask = (1 << (BinaryTrieLeafShift - 3)) - 178 out.write_byte_array(79 "\{property} trie top level: `cp >> \{BinaryTrieTopShift}` to mid block index",80 "\{prefix}_trie_top",81 mid.ids,82 )83 out.write_byte_array(84 "\{property} trie mid level: leaf block indices",85 "\{prefix}_trie_mid",86 mid.blocks,87 )88 out.write_byte_array(89 "\{property} trie leaf level: bitsets of \{1 << BinaryTrieLeafShift} code points, least significant bit first",90 "\{prefix}_trie_leaf",91 leaf.blocks,92 )93 out.write(94 (95 $|///|96 $|/// \{lookup_doc}97 $|\{visibility}fn \{lookup}(c : Char) -> Bool {98 $| let cp = c.to_int()99 $| if cp >= \{@emitter.hex_literal(BinaryTrieLimit)} {100 $| return \{high_check}101 $| }102 $| let mid = (\{prefix}_trie_top[cp >> \{BinaryTrieTopShift}].to_int() << \{BinaryTrieTopShift - BinaryTrieLeafShift}) |103 $| ((cp >> \{BinaryTrieLeafShift}) & \{mid_mask})104 $| let leaf = \{prefix}_trie_mid[mid].to_int()105 $| let bits = \{prefix}_trie_leaf[(leaf << \{BinaryTrieLeafShift - 3}) | ((cp >> 3) & \{byte_mask})].to_int()106 $| ((bits >> (cp & 7)) & 1) != 0107 $|}108 $|109 ),110 )111}112113///|114/// Emit a data file holding the trie and lookup function of the binary115/// property `property`, read from the UCD file `content`, whose name is116/// `source`.117pub fn emit_binary_property(118 content : String,119 property~ : String,120 source~ : String,121) -> String raise {122 let out = @emitter.Emitter::new()123 out.write_file_header("\{property} lookup data", source)124 write_binary_property_trie(125 out,126 property~,127 parse_property_ranges(content, property),128 )129 out.finish()130}131132///|133/// Emit XID_Start and XID_Continue from `DerivedCoreProperties.txt`.134pub fn emit_xid(content : String) -> String raise {135 let xid_start = parse_property_ranges(content, "XID_Start")136 let xid_continue = parse_property_ranges(content, "XID_Continue")137 validate_xid_subset(xid_start, xid_continue)138 let out = @emitter.Emitter::new()139 out.write_file_header(140 "XID_Start and XID_Continue lookup data", "DerivedCoreProperties.txt",141 )142 write_binary_property_trie(out, property="XID_Start", xid_start)143 write_binary_property_trie(out, property="XID_Continue", xid_continue)144 out.finish()145}146147///|148/// Emit the emoji properties of `emoji-data.txt` and the characters149/// `emoji-variation-sequences.txt` lists a variation sequence for.150pub fn emit_emoji(151 emoji_data : String,152 variation_sequences : String,153) -> String raise {154 let out = @emitter.Emitter::new()155 out.write_file_header(156 "Extended_Pictographic, Emoji_Presentation, Emoji_Modifier, Emoji_Modifier_Base, and emoji variation sequence lookup data",157 "emoji-data.txt and emoji-variation-sequences.txt",158 )159 for160 property in [161 "Extended_Pictographic", "Emoji_Presentation", "Emoji_Modifier", "Emoji_Modifier_Base",162 ] {163 write_binary_property_trie(164 out,165 property~,166 parse_property_ranges(emoji_data, property),167 )168 }169 write_binary_property_trie(170 out,171 property="Emoji_Variation_Sequence",172 lookup="has_emoji_variation_sequence",173 lookup_doc="Check whether a character starts an emoji variation sequence",174 parse_emoji_variation_sequences(variation_sequences),175 )176 out.finish()177}178179///|180/// Emit an independent punctuation table (General_Category group P). Keeping181/// it separate means code that only tests punctuation does not link the182/// General_Category trie.183pub fn emit_punctuation(data : UnicodeData) -> String raise {184 // Pc, Pd, Ps, Pe, Pi, Pf, and Po are ordinals 14 to 20.185 let ranges = ranges_where(data.general_categories, gc => gc >= 14 && gc <= 20)186 let out = @emitter.Emitter::new()187 out.write_file_header(188 "Punctuation (General_Category group P) lookup data", "UnicodeData.txt",189 )190 write_binary_property_trie(191 out,192 property="Punctuation",193 lookup_doc="Check whether a character is punctuation (General_Category group P)",194 ranges,195 )196 out.finish()197}198
///|
/// Binary property tries cover planes 0-3, like the General_Category trie.
/// The few ranges above are checked with explicit comparisons instead.
const BinaryTrieLimit : Int32 = 0x40000
///|
/// Each top-level trie entry covers `1 << BinaryTrieTopShift` code points.
const BinaryTrieTopShift : Int32 = 10
///|
/// Each leaf block is a bitset of `1 << BinaryTrieLeafShift` code points.
const BinaryTrieLeafShift : Int32 = 7
///|
/// Write a binary property as a three-level bitset trie for planes 0-3
/// named `<prefix>_trie_top`, `<prefix>_trie_mid`, and `<prefix>_trie_leaf`,
/// followed by the lookup function `is_<prefix>`, where `<prefix>` is the
/// property name in lowercase (`White_Space` becomes `white_space`).
///
/// A set of code points that is not a Unicode property passes `lookup`, the
/// name of the lookup function, and `lookup_doc`, its one-line description.
/// Set `exported=false` for a lookup used only inside its generated package.
///
/// The top level maps `cp >> 10` to a mid block, the mid level maps the next
/// three bits to a leaf block, and each leaf block holds one bit per code
/// point for 128 code points. Identical blocks are shared at both levels.
fn write_binary_property_trie(
out : @emitter.Emitter,
property~ : String,
lookup? : String,
lookup_doc? : String,
exported~ : Bool = true,
ranges : Array[@parsing.CodePointRange],
) -> Unit raise {
let prefix = property.to_lower()
let visibility = if exported { "pub " } else { "" }
let lookup = lookup.unwrap_or("is_\{prefix}")
let lookup_doc = lookup_doc.unwrap_or(
"Check whether a character has the Unicode \{property} property",
)
let bits = Array::make(BinaryTrieLimit / 8, 0)
let high_ranges : Array[@parsing.CodePointRange] = []
for range in ranges {
for cp in range.start..<=Int32::min(range.end, BinaryTrieLimit - 1) {
bits[cp >> 3] = bits[cp >> 3] | (1 << (cp & 7))
}
if range.end >= BinaryTrieLimit {
high_ranges.push({
start: Int32::max(range.start, BinaryTrieLimit),
end: range.end,
})
}
}
// Leaf level: bitset blocks; `leaf.ids` has one entry per leaf block.
let leaf = @emitter.deduplicate_blocks(bits, 1 << (BinaryTrieLeafShift - 3))
// Mid level: blocks of leaf block indices; `mid.ids` is the top level.
let mid = @emitter.deduplicate_blocks(
leaf.ids,
1 << (BinaryTrieTopShift - BinaryTrieLeafShift),
)
guard mid.ids.all(id => id < 0x100) else {
fail("\{property} trie has too many mid blocks for one byte")
}
guard mid.blocks.all(id => id < 0x100) else {
fail("\{property} trie has too many leaf blocks for one byte")
}
let high_check = if high_ranges.is_empty() {
"false"
} else {
high_ranges
.map(range => {
"(cp >= \{@emitter.hex_literal(range.start)} && cp <= \{@emitter.hex_literal(range.end)})"
})
.join(" || ")
}
let mid_mask = (1 << (BinaryTrieTopShift - BinaryTrieLeafShift)) - 1
let byte_mask = (1 << (BinaryTrieLeafShift - 3)) - 1
out.write_byte_array(
"\{property} trie top level: `cp >> \{BinaryTrieTopShift}` to mid block index",
"\{prefix}_trie_top",
mid.ids,
)
out.write_byte_array(
"\{property} trie mid level: leaf block indices",
"\{prefix}_trie_mid",
mid.blocks,
)
out.write_byte_array(
"\{property} trie leaf level: bitsets of \{1 << BinaryTrieLeafShift} code points, least significant bit first",
"\{prefix}_trie_leaf",
leaf.blocks,
)
out.write(
(
$|///|
$|/// \{lookup_doc}
$|\{visibility}fn \{lookup}(c : Char) -> Bool {
$| let cp = c.to_int()
$| if cp >= \{@emitter.hex_literal(BinaryTrieLimit)} {
$| return \{high_check}
$| }
$| let mid = (\{prefix}_trie_top[cp >> \{BinaryTrieTopShift}].to_int() << \{BinaryTrieTopShift - BinaryTrieLeafShift}) |
$| ((cp >> \{BinaryTrieLeafShift}) & \{mid_mask})
$| let leaf = \{prefix}_trie_mid[mid].to_int()
$| let bits = \{prefix}_trie_leaf[(leaf << \{BinaryTrieLeafShift - 3}) | ((cp >> 3) & \{byte_mask})].to_int()
$| ((bits >> (cp & 7)) & 1) != 0
$|}
$|
),
)
}
///|
/// Emit a data file holding the trie and lookup function of the binary
/// property `property`, read from the UCD file `content`, whose name is
/// `source`.
pub fn emit_binary_property(
content : String,
property~ : String,
source~ : String,
) -> String raise {
let out = @emitter.Emitter::new()
out.write_file_header("\{property} lookup data", source)
write_binary_property_trie(
out,
property~,
parse_property_ranges(content, property),
)
out.finish()
}
///|
/// Emit XID_Start and XID_Continue from `DerivedCoreProperties.txt`.
pub fn emit_xid(content : String) -> String raise {
let xid_start = parse_property_ranges(content, "XID_Start")
let xid_continue = parse_property_ranges(content, "XID_Continue")
validate_xid_subset(xid_start, xid_continue)
let out = @emitter.Emitter::new()
out.write_file_header(
"XID_Start and XID_Continue lookup data", "DerivedCoreProperties.txt",
)
write_binary_property_trie(out, property="XID_Start", xid_start)
write_binary_property_trie(out, property="XID_Continue", xid_continue)
out.finish()
}
///|
/// Emit the emoji properties of `emoji-data.txt` and the characters
/// `emoji-variation-sequences.txt` lists a variation sequence for.
pub fn emit_emoji(
emoji_data : String,
variation_sequences : String,
) -> String raise {
let out = @emitter.Emitter::new()
out.write_file_header(
"Extended_Pictographic, Emoji_Presentation, Emoji_Modifier, Emoji_Modifier_Base, and emoji variation sequence lookup data",
"emoji-data.txt and emoji-variation-sequences.txt",
)
for
property in [
"Extended_Pictographic", "Emoji_Presentation", "Emoji_Modifier", "Emoji_Modifier_Base",
] {
write_binary_property_trie(
out,
property~,
parse_property_ranges(emoji_data, property),
)
}
write_binary_property_trie(
out,
property="Emoji_Variation_Sequence",
lookup="has_emoji_variation_sequence",
lookup_doc="Check whether a character starts an emoji variation sequence",
parse_emoji_variation_sequences(variation_sequences),
)
out.finish()
}
///|
/// Emit an independent punctuation table (General_Category group P). Keeping
/// it separate means code that only tests punctuation does not link the
/// General_Category trie.
pub fn emit_punctuation(data : UnicodeData) -> String raise {
// Pc, Pd, Ps, Pe, Pi, Pf, and Po are ordinals 14 to 20.
let ranges = ranges_where(data.general_categories, gc => gc >= 14 && gc <= 20)
let out = @emitter.Emitter::new()
out.write_file_header(
"Punctuation (General_Category group P) lookup data", "UnicodeData.txt",
)
write_binary_property_trie(
out,
property="Punctuation",
lookup_doc="Check whether a character is punctuation (General_Category group P)",
ranges,
)
out.finish()
}