unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

tools/emitter/value_trie.mbt
1///|2/// Value tries cover planes 0-3; the higher planes hold few distinct runs and3/// are looked up as packed ranges instead.4const ValueTrieLimit : Int32 = 0x4000056///|7/// Each top-level trie entry covers `1 << ValueTrieTopShift` code points.8const ValueTrieTopShift : Int32 = 8910///|11/// Each leaf block holds `1 << ValueTrieLeafShift` values.12const ValueTrieLeafShift : Int32 = 41314///|15/// Write a table holding one small integer per code point, followed by its16/// lookup function.17///18/// Planes 0-3 become a three-level trie named `<prefix>_trie_top`,19/// `<prefix>_trie_mid`, and `<prefix>_trie_leaf`: the top level maps20/// `cp >> 8` to a mid block, the mid level maps the next four bits to a leaf21/// block, and the leaf level stores one value per code point, in one byte or,22/// when `value_bits` exceeds 8, in 16 bits. Identical blocks are shared at23/// both levels. The remaining planes become `<prefix>_high_ranges`, packed as24/// `start << range_value_bits | value`.25///26/// The mid level holds one leaf block index per `Int`, so that the step every27/// lookup takes is a single load. Reading two bytes per index instead costs a28/// second bounds-checked load, which made the General_Category trie 1.4-1.829/// times as slow on wasm and JS; packing two indices per `Int` leaves a shift30/// and a mask on the path to the leaf load, which made it about 5% slower on31/// native than two bytes. A `ReadOnlyArray[UInt16]` would be as fast and half32/// the size, but moonc builds it on wasm-gc with one `array.set` per element33/// instead of from a data segment.34///35/// 16-bit leaf values are packed two to an `Int`, the even value in the low36/// half, since the leaf level is the largest and its value is the result.37/// The pairs are written in decimal, since a pair whose high half has its top38/// bit set is negative.39///40/// `values` holds the value of every code point, each below41/// `1 << value_bits`, and below `1 << range_value_bits` from U+40000 on;42/// `range_value_bits` defaults to `value_bits`. `lookup` is the declaration43/// head of the lookup44/// function, such as `pub fn lookup_east_asian_width`; it takes a `Char`, or45/// the code point as an `Int` when `takes_code_point` is set, and returns the46/// value as an `Int`. `lookup_doc` is its documentation, one entry per line.47pub fn Emitter::write_value_trie(48  self : Emitter,49  property~ : String,50  prefix~ : String,51  lookup~ : String,52  lookup_doc~ : Array[String],53  value_bits~ : Int32,54  range_value_bits~ : Int32 = value_bits,55  takes_code_point~ : Bool = false,56  values : FixedArray[Int32],57) -> Unit raise {58  guard values.length() == MaxCodePoint + 1 else {59    fail("\{property} table must hold one value per code point")60  }61  guard value_bits <= 16 && range_value_bits <= value_bits else {62    fail("\{property} trie values must fit in 16 bits")63  }64  guard values.all(value => value >= 0 && value < 1 << value_bits) else {65    fail("\{property} value does not fit in \{value_bits} bits")66  }67  // `start << range_value_bits | value`, so the packed values sort by start68  // code point.69  let high_ranges = []70  for cp in ValueTrieLimit..<=MaxCodePoint {71    guard values[cp] < 1 << range_value_bits else {72      fail(73        "\{property} value at \{hex_literal(cp)} does not fit in \{range_value_bits} bits",74      )75    }76    if cp == ValueTrieLimit || values[cp] != values[cp - 1] {77      high_ranges.push((cp << range_value_bits) | values[cp])78    }79  }80  // Leaf level: blocks of values.81  let leaf = deduplicate_blocks(82    Array::makei(ValueTrieLimit, cp => values[cp]),83    1 << ValueTrieLeafShift,84  )85  // Mid level: blocks of leaf block indices; `mid.ids` is the top level.86  let mid = deduplicate_blocks(87    leaf.ids,88    1 << (ValueTrieTopShift - ValueTrieLeafShift),89  )90  guard mid.ids.all(id => id < 0x100) else {91    fail("\{property} trie has too many mid blocks for one byte")92  }93  guard mid.blocks.all(id => id < 0x10000) else {94    fail("\{property} trie has too many leaf blocks for two bytes")95  }96  let trie_limit = hex_literal(ValueTrieLimit)97  let mid_mask = (1 << (ValueTrieTopShift - ValueTrieLeafShift)) - 198  let leaf_mask = (1 << ValueTrieLeafShift) - 199  let range_mask = (1 << range_value_bits) - 1100  let wide = value_bits > 8101  self.write_byte_array(102    "\{property} trie top level: `cp >> \{ValueTrieTopShift}` to mid block index",103    "\{prefix}_trie_top",104    mid.ids,105  )106  self.write_int_array(107    "\{property} trie mid level: leaf block indices",108    "\{prefix}_trie_mid",109    mid.blocks,110    hex=false,111  )112  if wide {113    self.write_int_array(114      "\{property} trie leaf level: 16-bit values in blocks of \{1 << ValueTrieLeafShift}, two per entry",115      "\{prefix}_trie_leaf",116      pack_16_bit_pairs(leaf.blocks),117      hex=false,118    )119  } else {120    self.write_byte_array(121      "\{property} trie leaf level: values in blocks of \{1 << ValueTrieLeafShift}",122      "\{prefix}_trie_leaf",123      leaf.blocks,124    )125  }126  self.write_int_array(127    "\{property} ranges from \{trie_limit} packed as `start << \{range_value_bits} | value`",128    "\{prefix}_high_ranges",129    high_ranges,130    hex=true,131  )132  self.write("///|\n")133  for line in lookup_doc {134    self.write_line("/// \{line}")135  }136  self.write(137    if takes_code_point {138      "\{lookup}(cp : Int) -> Int {\n"139    } else {140      "\{lookup}(c : Char) -> Int {\n  let cp = c.to_int()\n"141    },142  )143  self.write(144    (145      $|  if cp >= \{trie_limit} {146      $|    // Binary search for the last range starting at or before `cp`.147      $|    let key = (cp << \{range_value_bits}) | \{range_mask}148      $|    let mut low = 0149      $|    let mut high = \{prefix}_high_ranges.length()150      $|    while high - low > 1 {151      $|      let mid = (low + high) / 2152      $|      if \{prefix}_high_ranges[mid] <= key {153      $|        low = mid154      $|      } else {155      $|        high = mid156      $|      }157      $|    }158      $|    return \{prefix}_high_ranges[low] & \{range_mask}159      $|  }160      $|  let mid = (\{prefix}_trie_top[cp >> \{ValueTrieTopShift}].to_int() << \{ValueTrieTopShift - ValueTrieLeafShift}) |161      $|    ((cp >> \{ValueTrieLeafShift}) & \{mid_mask})162      $|  let leaf = \{prefix}_trie_mid[mid]163      $|164    ),165  )166  self.write(167    if wide {168      (169        $|  let offset = (leaf << \{ValueTrieLeafShift}) | (cp & \{leaf_mask})170        $|  (\{prefix}_trie_leaf[offset >> 1] >> ((offset & 1) << 4)) & 0xFFFF171        $|}172        $|173      )174    } else {175      (176        $|  \{prefix}_trie_leaf[(leaf << \{ValueTrieLeafShift}) | (cp & \{leaf_mask})].to_int()177        $|}178        $|179      )180    },181  )182}183184///|185/// Pack 16-bit values two to an `Int`: value `2 * i` in the low half of entry186/// `i` and value `2 * i + 1` in the high half. An odd count leaves the last187/// high half zero.188fn pack_16_bit_pairs(values : Array[Int32]) -> Array[Int32] {189  Array::makei((values.length() + 1) / 2, i => {190    let high = if 2 * i + 1 < values.length() { values[2 * i + 1] } else { 0 }191    values[2 * i] | (high << 16)192  })193}194