unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

tools/ucd/binary_property.mbt
1///|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