unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

normalization/quick_check.mbt
1///|2/// The normalization record of a character: its packed properties in bits3/// 0..15, and in the bits above, where `@decomposition.packed_decomposition`4/// finds its decomposition. ASCII has CCC=0, Quick_Check=Yes for every5/// normalization form and no decomposition.6fn normalization_record(c : Char) -> Int32 {7  if c.to_int() < 0x80 {8    09  } else {10    @decomposition.lookup_normalization_record(c)11  }12}1314///|15/// The Quick_Check bits of NFC and NFKC, the forms that compose: Yes=0,16/// No=1, Maybe=2.17const ComposeQuickCheckMask : Int32 = 31819///|20/// Check suspect segments of NFC or NFKC, composed in `composer`, until a21/// clean run. Return its next unconsumed boundary, or -1 if checking fails.22fn check_suspect_spans(23  composer : Composer,24  s : StringView,25  start : Int32,26  problem_offset : Int32,27  shift : Int32,28  compatibility~ : Bool,29) -> Int32 {30  // Retain the starter and any preceding marks in the first suspect segment.31  for c in s[start:problem_offset] {32    composer.append(c.to_int(), normalization_record(c), compatibility~)33  }34  let mut span_start = start35  let mut offset = problem_offset36  let mut previous_ccc = 037  let mut suspect = true38  let mut clean_start = problem_offset39  for c in s[problem_offset:] {40    let record = normalization_record(c)41    let ccc = record & 25542    let check = (record >> shift) & ComposeQuickCheckMask43    if ccc == 0 && check == 0 {44      // Amortize the handoff over a clean run: consume up to two UTF-16 units45      // here before resuming the tight scanner. Dense one/two-starter gaps46      // stay in this loop, reusing their already loaded properties.47      if !suspect && previous_ccc == 0 && offset - clean_start >= 2 {48        return offset49      }50      if suspect {51        if !composer.check(s[span_start:offset]) {52          return -153        }54        clean_start = offset55      }56      span_start = offset57      suspect = false58    }59    let out_of_order = ccc != 0 && previous_ccc > ccc60    if check == 1 || out_of_order {61      return -162    }63    if !suspect && check != 0 {64      for preceding in s[span_start:offset] {65        composer.append(66          preceding.to_int(),67          normalization_record(preceding),68          compatibility~,69        )70      }71      suspect = true72    }73    if suspect {74      composer.append(c.to_int(), record, compatibility~)75    }76    previous_ccc = ccc77    offset += if c.to_int() > 0xFFFF { 2 } else { 1 }78  }79  if suspect && !composer.check(s[span_start:offset]) {80    return -181  }82  offset83}8485///|86/// Skip Quick_Check=Yes, CCC=0 characters from `start` and return the offset87/// of the first other character. Without one before `end`, return `end`, or88/// one past it when a surrogate pair crosses it. `slow_mask` selects CCC and89/// one form's Quick_Check bits of the packed properties; shifted right by90/// seven it selects the same bits of the generated scan flags.91/// Offsets are absolute in the backing string. `limit` is the view's end;92/// a pair may cross the current scan chunk's `end`, but never `limit`.93///94/// The loop reads the generated one-byte flags and makes no calls. Looking95/// properties up through `@ccc` instead costs a call per character, because96/// functions are not inlined across packages. Even one call on a rare path97/// would make every entry to this function save and restore registers, which98/// shows on text with many short runs. The loop is also sensitive to its99/// shape: trying blocks inside it instead of around it costs an extra taken100/// branch per character.101fn scan_clean_units(102  s : String,103  start : Int32,104  end : Int32,105  limit : Int32,106  slow_mask : Int32,107) -> Int32 {108  let scan_mask = slow_mask >> 7109  let unit_mask = scan_mask | NormalizationScanLeadSurrogate110  let mut offset = start111  while offset < end {112    // SAFETY: offset starts at a nonnegative boundary and offset < end <= limit <= s.length().113    // It advances by two only after checking that a second unit exists.114    let first = s.unsafe_get(offset).to_int()115    // SAFETY: first is a UTF-16 code unit, so first >> NormalizationScanShift116    // indexes one of the 2048 blocks; the generator checks every flags index.117    let block = normalization_scan_index118      .unsafe_get(first >> NormalizationScanShift)119      .to_int()120    let flags = normalization_scan_flags121      .unsafe_get(122        (block << NormalizationScanShift) | (first & NormalizationScanBlockMask),123      )124      .to_int()125    if (flags & unit_mask) == 0 {126      offset += 1127      continue128    }129    if flags != NormalizationScanLeadSurrogate {130      break131    }132    // An unpaired surrogate has default properties.133    if offset + 1 >= limit {134      offset += 1135      continue136    }137    // SAFETY: offset + 1 < limit is checked above.138    let second = s.unsafe_get(offset + 1).to_int()139    if second < 0xDC00 || second > 0xDFFF {140      offset += 1141      continue142    }143    let lead = first - 0xD800144    // Compare the default-tail boundary before reading the group summary.145    // SAFETY: a valid pair outside that tail has a generated lead index.146    if lead > NormalizationTailLeadIndex ||147      (lead == NormalizationTailLeadIndex && second >= NormalizationTailTrail) ||148      (normalization_lead_flags.unsafe_get(lead).to_int() & scan_mask) == 0 {149      offset += 2150      continue151    }152    // Some character in this group of 1024 has flags: read this pair's own.153    // SAFETY: lead is below the tail as above and trail is a 10-bit value;154    // the generator checks both indices for every such pair.155    let trail = second - 0xDC00156    let slot = normalization_lead_slots.unsafe_get(lead).to_int()157    let pair_block = normalization_pair_index158      .unsafe_get(159        (slot << (10 - NormalizationPairShift)) |160        (trail >> NormalizationPairShift),161      )162      .to_int()163    let pair_flags = normalization_pair_flags164      .unsafe_get(165        (pair_block << NormalizationPairShift) |166        (trail & NormalizationPairBlockMask),167      )168      .to_int()169    if (pair_flags & scan_mask) != 0 {170      break171    }172    offset += 2173  }174  offset175}176177///|178/// Return the end of the run of clean characters starting at `start`.179///180/// Once a stretch of code units has passed the scan one at a time, blocks181/// are tried: a block whose code units are all below the clean limit needs182/// no table. The stretch starts short, so that a run that soon ends never183/// reaches a block, and grows while no block is clean, so that text above the184/// limit pays for few tries and few calls. On native and wasm, later185/// stretches are scanned four units at a time, which takes fewer branches per186/// unit but costs more where the run ends, so the first stretch, where most187/// short runs end, is not.188fn scan_clean_run(189  s : String,190  start : Int32,191  end : Int32,192  slow_mask : Int32,193) -> Int32 {194  let mut offset = start195  let mut stretch = MinUnitStretch196  while true {197    let chunk_end = if end - offset > stretch { offset + stretch } else { end }198    if offset > start {199      offset = skip_clean_quads(s, offset, chunk_end, slow_mask >> 7)200    }201    offset = scan_clean_units(s, offset, chunk_end, end, slow_mask)202    // A pair that crosses `chunk_end` leaves the offset one past it.203    if offset < chunk_end || offset >= end {204      break205    }206    let blocks_end = skip_clean_blocks(s, offset, end, slow_mask >> 7)207    if blocks_end > offset {208      stretch = MinUnitStretch209    } else if stretch < MaxUnitStretch {210      stretch = 4 * stretch211    }212    offset = blocks_end213  }214  offset215}216217///|218/// Without SIMD, the scan one unit at a time is faster than groups of four.219#cfg(not(any(target="native", target="wasm")))220fn skip_clean_quads(221  _s : String,222  start : Int32,223  _end : Int32,224  _scan_mask : Int32,225) -> Int32 {226  start227}228229///|230/// Skip groups of four code units that are all clean. A lead surrogate231/// stops the skip; the scan one unit at a time handles it.232#cfg(any(target="native", target="wasm"))233fn skip_clean_quads(234  s : String,235  start : Int32,236  end : Int32,237  scan_mask : Int32,238) -> Int32 {239  let unit_mask = scan_mask | NormalizationScanLeadSurrogate240  let mut offset = start241  while end - offset >= 4 {242    // SAFETY: four units remain before `end`.243    let flags = unit_scan_flags(s.unsafe_get(offset)) |244      unit_scan_flags(s.unsafe_get(offset + 1)) |245      unit_scan_flags(s.unsafe_get(offset + 2)) |246      unit_scan_flags(s.unsafe_get(offset + 3))247    if (flags & unit_mask) != 0 {248      break249    }250    offset += 4251  }252  offset253}254255///|256/// The scan flags of one code unit.257#cfg(any(target="native", target="wasm"))258fn unit_scan_flags(unit : UInt16) -> Int32 {259  let unit = unit.to_int()260  // SAFETY: a code unit shifted by NormalizationScanShift indexes one of the261  // 2048 blocks; the generator checks every flags index.262  normalization_scan_flags263  .unsafe_get(264    (265      normalization_scan_index266      .unsafe_get(unit >> NormalizationScanShift)267      .to_int() <<268      NormalizationScanShift269    ) |270    (unit & NormalizationScanBlockMask),271  )272  .to_int()273}274275///|276/// Code units scanned one at a time before the first block and after a block277/// that is not clean.278const MinUnitStretch : Int32 = 16279280///|281const MaxUnitStretch : Int32 = 4096282283///|284/// The first code unit that is not a clean starter in the forms `scan_mask`285/// selects: U+00A0 has a compatibility mapping, U+00C0 a canonical one, and286/// U+0300 is the first combining mark. The wasm-gc skip tests the287/// `scan_mask` bits inline instead.288#cfg(not(target="wasm-gc"))289fn clean_unit_limit(scan_mask : Int32) -> Int32 {290  if (scan_mask & 0b1011000) != 0 {291    0xA0292  } else if (scan_mask & 0b0100000) != 0 {293    0xC0294  } else {295    0x300296  }297}298299///|300/// Skip blocks of four code units that are all below the clean limit, and301/// return the offset of the first block that is not, or that is incomplete.302/// Without SIMD, comparing the units' union is one test per block, against303/// the largest power of two at or below the limit: U+0200 for NFC, which304/// covers Latin Extended-A, and ASCII for the other forms.305#cfg(target="wasm-gc")306fn skip_clean_blocks(307  s : String,308  start : Int32,309  end : Int32,310  scan_mask : Int32,311) -> Int32 {312  // `clean_unit_limit` is 0x300 exactly when none of these forms is selected.313  // Tested here, since a call stays a call on wasm-gc: calling it made NFD314  // 6-8% slower there on x86.315  let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }316  let mut offset = start317  while end - offset >= 4 {318    // SAFETY: four units remain before `end`.319    let units = s.unsafe_get(offset) |320      s.unsafe_get(offset + 1) |321      s.unsafe_get(offset + 2) |322      s.unsafe_get(offset + 3)323    if units.to_int() >= limit {324      break325    }326    offset += 4327  }328  offset329}330331///|332/// The loop of the wasm-gc `skip_clean_blocks`, for a JS view that ends333/// before its string.334#cfg(target="js")335fn skip_low_unit_blocks(336  s : String,337  start : Int32,338  end : Int32,339  scan_mask : Int32,340) -> Int32 {341  // The test of the wasm-gc version, for the same `scan_mask` bits.342  let limit = if (scan_mask & 0b1111000) == 0 { 0x200 } else { 0x80 }343  let mut offset = start344  while end - offset >= 4 {345    // SAFETY: four units remain before `end`.346    let units = s.unsafe_get(offset) |347      s.unsafe_get(offset + 1) |348      s.unsafe_get(offset + 2) |349      s.unsafe_get(offset + 3)350    if units.to_int() >= limit {351      break352    }353    offset += 4354  }355  offset356}357358///|359/// Skip code units that are all below the clean limit, and return the offset360/// of the first that is not. A sticky regular expression scans the string in361/// V8's compiled matcher, about three times as fast on ASCII as reading the362/// units one at a time; it stops only at a unit it rejects or at the string's363/// end, so a view that ends early is scanned with the loop instead.364#cfg(target="js")365fn skip_clean_blocks(366  s : String,367  start : Int32,368  end : Int32,369  scan_mask : Int32,370) -> Int32 {371  let limit = clean_unit_limit(scan_mask)372  // SAFETY: start < end is checked first. A run often ends at its first373  // unit, as in Cyrillic text, and the call into the matcher costs more374  // than that test.375  if start >= end || s.unsafe_get(start).to_int() >= limit {376    start377  } else if end == s.length() {378    skip_units_below(s, start, limit)379  } else {380    skip_low_unit_blocks(s, start, end, scan_mask)381  }382}383384///|385/// The offset of the first code unit of `s` from `start` that is not below386/// `limit`, one of the results of `clean_unit_limit`, or `s.length()`.387#cfg(target="js")388extern "js" fn skip_units_below(389  s : String,390  start : Int32,391  limit : Int32,392) -> Int32 =393  #|(() => {394  #|  const below = { 0xa0: /[\0-\x9f]*/y, 0xc0: /[\0-\xbf]*/y, 0x300: /[\0-\u02ff]*/y };395  #|  return (s, start, limit) => {396  #|    const re = below[limit];397  #|    re.lastIndex = start;398  #|    re.test(s);399  #|    return re.lastIndex;400  #|  };401  #|})()402403///|404/// Skip blocks of eight code units that are all below the clean limit, and405/// return the offset of the first block that is not, or that is incomplete.406///407/// A unit at or above the limit is the one that leaves a lane nonzero after408/// subtracting `limit - 1` with saturation. That takes one instruction on409/// SSE2, which has no unsigned 16-bit comparison, and two blocks are tested410/// per step. With a comparison and one block per step, the loop took 60-86%411/// longer on the x86 CI runners (AMD EPYC 7763 and 9V74) once a change to412/// unrelated tables moved it, though its code was the same: about 4 cycles413/// per block instead of 2.5.414#cfg(target="native")415// The SIMD operations are experimental upstream. Only this function uses416// them, so the alert is silenced here and not for the whole package.417#warnings("-alert_experimental")418fn skip_clean_blocks(419  s : String,420  start : Int32,421  end : Int32,422  scan_mask : Int32,423) -> Int32 {424  let below = @v128.i16x8_splat((clean_unit_limit(scan_mask) - 1).to_uint16())425  let mut offset = start426  while end - offset >= 16 {427    // SAFETY: offset is absolute and sixteen units remain before the view's428    // end.429    let excess = @v128.v128_or_(430      @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below),431      @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset + 8), below),432    )433    if @v128.v128_any_true(excess) {434      break435    }436    offset += 16437  }438  // The first block of a pair that failed may still be clean.439  while end - offset >= 8 {440    // SAFETY: offset is absolute and eight units remain before the view's end.441    let excess = @v128.i16x8_sub_sat_u(@v128.v128_load_i16x8(s, offset), below)442    if @v128.v128_any_true(excess) {443      break444    }445    offset += 8446  }447  offset448}449450///|451/// Skip blocks of eight code units that are all below the clean limit, and452/// return the offset of the first block that is not, or that is incomplete.453///454/// The native version tests two blocks per step; here that made NFD on455/// Cyrillic text 30-38% slower in V8, though it halved the time on ASCII.456#cfg(target="wasm")457// The SIMD operations are experimental upstream. Only this function uses458// them, so the alert is silenced here and not for the whole package.459#warnings("-alert_experimental")460fn skip_clean_blocks(461  s : String,462  start : Int32,463  end : Int32,464  scan_mask : Int32,465) -> Int32 {466  let limit = @v128.i16x8_splat(clean_unit_limit(scan_mask).to_uint16())467  let mut offset = start468  while end - offset >= 8 {469    // SAFETY: offset is absolute and eight units remain before the view's end.470    let block = @v128.v128_load_i16x8(s, offset)471    if @v128.v128_any_true(@v128.i16x8_ge_u(block, limit)) {472      break473    }474    offset += 8475  }476  offset477}478479///|480/// Scan UTF-16 with one cursor. The clean-run scan only skips Quick_Check=Yes,481/// CCC=0 characters; CCC ordering and boundary recovery live outside that loop.482/// When it stops, the last skipped code point is the preceding safe boundary.483/// Checking returns None on a difference and Some("") on success, without484/// copying the input. Normalization returns Some with the normalized string.485/// String? uses the native nullable-pointer representation; StringView? would486/// allocate an Option wrapper even when the input is already normalized.487fn process_spans(488  s : StringView,489  shift : Int32,490  mask : Int32,491  compatibility~ : Bool,492  compose~ : Bool,493  check_only~ : Bool,494) -> String? {495  let data = s.data()496  let start = s.start_offset()497  let end = start + s.length()498  let slow_mask = 255 | (mask << shift)499  let mut offset = start500  let mut span_start = start501  let mut previous_ccc = 0502  while offset < end {503    let run_start = offset504    offset = scan_clean_run(data, offset, end, slow_mask)505    if offset == end {506      return Some(if check_only { "" } else { s.to_owned() })507    }508    // SAFETY: start <= offset < end <= data.length().509    let mut cp = data.unsafe_get(offset).to_int()510    let mut width = 1511    if cp >= 0xD800 && cp <= 0xDBFF {512      // The scan stops on a leading surrogate only when a trailing one follows.513      cp = 0x10000 + ((cp - 0xD800) << 10) + data[offset + 1].to_int() - 0xDC00514      width = 2515    }516    let properties = @ccc.lookup_normalization_properties(cp.unsafe_to_char())517    if offset > run_start {518      // All skipped characters are CCC=0 and Quick_Check=Yes. Recover only519      // the last one's start, including its leading surrogate when present.520      // Written out, not shared with the other two scans that do this: a521      // helper stays a call on wasm-gc, where this runs after every clean522      // run.523      span_start = offset - 1524      if data[span_start].is_trailing_surrogate() &&525        span_start > run_start &&526        data[span_start - 1].is_leading_surrogate() {527        span_start -= 1528      }529      previous_ccc = 0530    }531    let ccc = properties & 255532    let check = (properties >> shift) & mask533    let out_of_order = ccc != 0 && previous_ccc > ccc534    if check_only && (check == 1 || out_of_order) {535      return None536    }537    if check != 0 || out_of_order {538      if !check_only {539        let remaining_start = span_start - start540        return Some(541          if compose {542            compose_remaining(s, remaining_start, shift, compatibility~)543          } else {544            decompose_remaining(s, remaining_start, shift, compatibility~)545          },546        )547      }548      // Checking reaches this point only past Quick_Check=Maybe, which549      // only NFC and NFKC have.550      return if check_remaining_spans(551          s,552          span_start - start,553          offset - start,554          shift,555          compatibility~,556        ) {557        Some("")558      } else {559        None560      }561    }562    // Quick_Check=Yes marks still require ordering checks. Keep their starter563    // boundary until the next run of CCC=0 characters or a suspect character.564    previous_ccc = ccc565    offset += width566  }567  Some(if check_only { "" } else { s.to_owned() })568}569570///|571/// Check NFC or NFKC after the first suspect character, reusing one572/// composer, which writes nothing. Normal runs resume the tight scanner; the573/// allocation-free entry path keeps the scratch state out of its hot loop.574fn check_remaining_spans(575  s : StringView,576  start : Int32,577  problem_offset : Int32,578  shift : Int32,579  compatibility~ : Bool,580) -> Bool {581  let composer = Composer::new(0)582  let length = s.length()583  let data = s.data()584  let view_start = s.start_offset()585  let view_end = view_start + length586  let slow_mask = 255 | (ComposeQuickCheckMask << shift)587  let mut offset = problem_offset588  let mut span_start = start589  while offset < length {590    offset = check_suspect_spans(591      composer,592      s,593      span_start,594      offset,595      shift,596      compatibility~,597    )598    if offset < 0 {599      return false600    }601    // The helper stopped before a clean starter (or at the end). Scan the602    // following run without carrying scratch state through its loop.603    let run_start = offset604    // Suspect-segment processing uses view-relative offsets; convert only605    // at the handoff to the scanner, whose hot loop uses absolute offsets.606    offset = scan_clean_run(data, view_start + offset, view_end, slow_mask) -607      view_start608    if offset == length {609      break610    }611    // At least one clean starter was skipped. Retain its last code point for612    // the next segment, including the leading half of a surrogate pair.613    span_start = offset - 1614    if s[span_start].is_trailing_surrogate() &&615      span_start > run_start &&616      s[span_start - 1].is_leading_surrogate() {617      span_start -= 1618    }619  }620  true621}622623///|624fn normalize_spans(625  s : StringView,626  shift : Int32,627  mask : Int32,628  compatibility~ : Bool,629  compose~ : Bool,630) -> String {631  // Keep the fallback lazy without allocating a capturing closure.632  if process_spans(s, shift, mask, compatibility~, compose~, check_only=false)633    is Some(result) {634    result635  } else {636    s.to_owned()637  }638}639