unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

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