unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

punycode/punycode.mbt
1///|2/// Punycode encoding/decoding (RFC 3492)3/// Used for Internationalized Domain Names in Applications (IDNA)45///|6/// Error type for Punycode operations7pub(all) suberror PunycodeError {8  Overflow9  InvalidInput10  BadInput11}1213///|14pub extend PunycodeError with Show::{to_string, output}1516///|17pub impl Show for PunycodeError with fn output(self, logger) {18  match self {19    Overflow => logger.write_string("Overflow")20    InvalidInput => logger.write_string("InvalidInput")21    BadInput => logger.write_string("BadInput")22  }23}2425// RFC 3492 constants (Section 4)2627///|28/// Base for variable-length integer encoding. Punycode uses base-3629/// (letters a-z represent 0-25, digits 0-9 represent 26-35).30const Base : Int32 = 363132///|33/// Minimum threshold for variable-length integer encoding.34/// Ensures at least one digit is always output.35const Tmin : Int32 = 13637///|38/// Maximum threshold for variable-length integer encoding.39/// Equals the number of lowercase letters (a-z).40const Tmax : Int32 = 264142///|43/// Skew parameter for bias adaptation function.44/// Controls how quickly the bias adjusts to character frequencies.45const Skew : Int32 = 384647///|48/// Damping factor applied only to the first delta value.49/// Prevents the bias from changing too rapidly at the start.50const Damp : Int32 = 7005152///|53/// Initial bias value for the adaptation algorithm.54/// Chosen to work well for typical internationalized domain names.55const InitialBias : Int32 = 725657///|58/// Initial value of n, the threshold between basic ASCII (0-127)59/// and non-basic code points that require encoding.60const InitialN : Int32 = 0x806162///|63/// Delimiter character separating the basic ASCII portion64/// from the Punycode-encoded portion in the output.65const Delimiter : Char = '-'6667///|68/// Largest positive value representable by MoonBit's signed Int type.69const MaxInt : Int32 = 0x7FFFFFFF7071///|72/// Bias adaptation function (RFC 3492 Section 3.4)73fn adapt(delta : Int32, numpoints : Int32, firsttime : Bool) -> Int32 {74  let mut delta = delta75  if firsttime {76    delta = delta / Damp77  } else {78    delta = delta / 279  }80  delta = delta + delta / numpoints81  let mut k = 082  while delta > (Base - Tmin) * Tmax / 2 {83    delta = delta / (Base - Tmin)84    k = k + Base85  }86  k + (Base - Tmin + 1) * delta / (delta + Skew)87}8889///|90/// Encode a digit to a basic code point (a-z for 0-25, 0-9 for 26-35)91fn encode_digit(d : Int32) -> Char {92  if d < 26 {93    (d + 'a'.to_int()).unsafe_to_char()94  } else {95    (d - 26 + '0'.to_int()).unsafe_to_char()96  }97}9899///|100/// Decode a basic code point to a digit101fn decode_digit(cp : Int32) -> Int32 {102  if cp >= 'a'.to_int() && cp <= 'z'.to_int() {103    cp - 'a'.to_int()104  } else if cp >= 'A'.to_int() && cp <= 'Z'.to_int() {105    cp - 'A'.to_int()106  } else if cp >= '0'.to_int() && cp <= '9'.to_int() {107    cp - '0'.to_int() + 26108  } else {109    Base // Invalid110  }111}112113///|114/// Whether every code point of `input` is basic. Code units below `InitialN`115/// are exactly the basic code points, as surrogates are above it.116fn is_basic(input : StringView) -> Bool {117  for i in 0..<input.length() {118    if input.unsafe_get(i).to_int() >= InitialN {119      return false120    }121  }122  true123}124125///|126/// Encode a Unicode string to Punycode127pub fn encode(input : StringView) -> String raise PunycodeError {128  if is_basic(input) {129    // Only basic code points: they are copied, followed by the delimiter.130    return if input.is_empty() {131      ""132    } else if JsStrings {133      // `to_owned` does not copy a view of a whole string.134      input.to_owned() + "-"135    } else {136      basic_to_string(input)137    }138  }139  // Reserve the input and a few digits for each code unit; the size hint140  // counts bytes, two per UTF-16 code unit.141  let output = StringBuilder(capacity=2 * (1 + 4 * input.length()))142  ignore(encode_extended(input, output))143  output.to_string()144}145146///|147/// Encode a Unicode string to Punycode at the end of `output`, and return the148/// number of characters written, all of them ASCII.149///150/// When encoding fails, part of the encoding may already be in `output`.151pub fn encode_to(152  input : StringView,153  output : StringBuilder,154) -> Int32 raise PunycodeError {155  if is_basic(input) {156    // Only basic code points: they are copied, followed by the delimiter.157    if input.is_empty() {158      return 0159    }160    output.write_view(input)161    output.write_char(Delimiter)162    return input.length() + 1163  }164  encode_extended(input, output)165}166167///|168/// Encode `input`, which holds at least one code point that is not basic, at169/// the end of `output`, and return the number of characters written.170fn encode_extended(171  input : StringView,172  output : StringBuilder,173) -> Int32 raise PunycodeError {174  // The UTF-16 length bounds the number of code points.175  let code_points : FixedArray[Int32] = FixedArray::make(input.length(), 0)176  let mut count = 0177  let mut basic_count = 0178  for c in input {179    let cp = c.to_int()180    code_points[count] = cp181    count = count + 1182    if cp < InitialN {183      basic_count = basic_count + 1184    }185  }186  let mut written = 0187188  // Copy all basic code points to output189  for i in 0..<count {190    let cp = code_points[i]191    if cp < InitialN {192      output.write_char(cp.unsafe_to_char())193    }194  }195  written = basic_count196197  // Add delimiter if there were basic characters198  if basic_count > 0 {199    output.write_char(Delimiter)200    written = written + 1201  }202  let mut n = InitialN203  let mut delta = 0204  let mut bias = InitialBias205  let mut handled = basic_count206  while handled < count {207    // Find the minimum code point >= n208    let mut m = 0x10FFFF + 1209    for i in 0..<count {210      let cp = code_points[i]211      if cp >= n && cp < m {212        m = cp213      }214    }215216    // Increase delta enough to advance the decoder's <n,i> state to <m,0>217    let code_point_step = m - n218    let point_count = handled + 1219    if code_point_step > (MaxInt - delta) / point_count {220      raise Overflow221    }222    delta = delta + code_point_step * point_count223    n = m224    for i in 0..<count {225      let cp = code_points[i]226      if cp < n {227        if delta == MaxInt {228          raise Overflow229        }230        delta = delta + 1231      } else if cp == n {232        // Represent delta as a generalized variable-length integer233        let mut q = delta234        let mut k = Base235        while true {236          let t = if k <= bias {237            Tmin238          } else if k >= bias + Tmax {239            Tmax240          } else {241            k - bias242          }243          if q < t {244            break245          }246          output.write_char(encode_digit(t + (q - t) % (Base - t)))247          written = written + 1248          q = (q - t) / (Base - t)249          k = k + Base250        }251        output.write_char(encode_digit(q))252        written = written + 1253        bias = adapt(delta, handled + 1, handled == basic_count)254        delta = 0255        handled = handled + 1256      }257    }258    if delta == MaxInt {259      raise Overflow260    }261    delta = delta + 1262    n = n + 1263  }264  written265}266267///|268/// Decode a Punycode string to Unicode269pub fn decode(input : StringView) -> String raise PunycodeError {270  // Valid input is ASCII, so it is read as UTF-16 code units; any other271  // unit is rejected where it is reached.272  let length = input.length()273274  // Find the last delimiter275  let mut basic_end = -1276  for i = length - 1; i >= 0; i = i - 1 {277    if input[i].to_int() == Delimiter.to_int() {278      basic_end = i279      break280    }281  }282283  // Code points of the output. Each one consumes at least one code unit of284  // input, so the input length bounds their number.285  let output : FixedArray[Int32] = FixedArray::make(length, 0)286  let mut output_length = 0287288  // Copy basic code points before the last delimiter289  for i in 0..<basic_end {290    let unit = input[i].to_int()291    if unit >= InitialN {292      raise BadInput293    }294    output[i] = unit295    output_length = i + 1296  }297298  // Main decoding loop299  let mut n = InitialN300  let mut i_val = 0301  let mut bias = InitialBias302  let mut in_pos = if basic_end >= 0 { basic_end + 1 } else { 0 }303  // UTF-16 length of the output304  let mut output_units = output_length305  while in_pos < length {306    let oldi = i_val307    let mut w = 1308    let mut k = Base309    while true {310      if in_pos >= length {311        raise BadInput312      }313      let digit = decode_digit(input[in_pos].to_int())314      in_pos = in_pos + 1315      if digit >= Base {316        raise BadInput317      }318      if digit > (MaxInt - i_val) / w {319        raise Overflow320      }321      i_val = i_val + digit * w322      let t = if k <= bias {323        Tmin324      } else if k >= bias + Tmax {325        Tmax326      } else {327        k - bias328      }329      if digit < t {330        break331      }332      if w > MaxInt / (Base - t) {333        raise Overflow334      }335      w = w * (Base - t)336      k = k + Base337    }338    let out_len = output_length + 1339    bias = adapt(i_val - oldi, out_len, oldi == 0)340    if i_val / out_len > MaxInt - n {341      raise Overflow342    }343    n = n + i_val / out_len344    i_val = i_val % out_len345346    // Reject values that are not valid Unicode scalar values before building347    // the output string. Int::to_char also rejects surrogate code points.348    guard n.to_char() is Some(_) else { raise BadInput }349    // Insert n at position i_val.350    output.blit_to(351      output,352      len=output_length - i_val,353      src_offset=i_val,354      dst_offset=i_val + 1,355    )356    output[i_val] = n357    output_length = out_len358    output_units += if n > 0xFFFF { 2 } else { 1 }359    i_val = i_val + 1360  }361362  if JsStrings {363    // The size hint counts bytes, so the builder is filled exactly.364    let result = StringBuilder(capacity=2 * output_units)365    for i in 0..<output_length {366      result.write_char(output[i].unsafe_to_char())367    }368    return result.to_string()369  }370  code_points_to_string(output, output_length, output_units)371}372373///|374/// Whether strings are JS strings. These are cheaper to build by appending, as375/// a string builder does, than from an array of code units. Elsewhere an array376/// of code units becomes a string without a copy, while a builder or a377/// concatenation allocates a buffer as well as the string.378#cfg(target="js")379const JsStrings : Bool = true380381///|382#cfg(not(target="js"))383const JsStrings : Bool = false384385///|386/// The basic code points of `input` followed by the delimiter, as a string387/// allocated once.388fn basic_to_string(input : StringView) -> String {389  let length = input.length()390  let units : FixedArray[UInt16] = FixedArray::make(length + 1, 0)391  for i in 0..<length {392    // SAFETY: `i` is below the length of both `input` and `units`.393    units.unsafe_set(i, input.unsafe_get(i))394  }395  units.unsafe_set(length, Delimiter.to_int().to_uint16())396  uint16_array_to_string(units)397}398399///|400/// The string of the first `count` code points of `code_points`, which take401/// `units` UTF-16 code units. They are written into an array of that length,402/// which becomes the string without a copy.403fn code_points_to_string(404  code_points : FixedArray[Int32],405  count : Int32,406  units : Int32,407) -> String {408  let result : FixedArray[UInt16] = FixedArray::make(units, 0)409  let mut index = 0410  for i in 0..<count {411    let code_point = code_points[i]412    // SAFETY: `units` counts two units for each code point above U+FFFF and413    // one for every other, so every index is in bounds.414    if code_point > 0xFFFF {415      let offset = code_point - 0x10000416      result.unsafe_set(index, (0xD800 + (offset >> 10)).to_uint16())417      result.unsafe_set(index + 1, (0xDC00 + (offset & 0x3FF)).to_uint16())418      index += 2419    } else {420      result.unsafe_set(index, code_point.to_uint16())421      index += 1422    }423  }424  uint16_array_to_string(result)425}426427///|428/// Take ownership of UTF-16 code units as a string of the same length.429fn uint16_array_to_string(units : FixedArray[UInt16]) -> String = "%string.unsafe_from_uint16_fixedarray"430