punycode/punycode.mbt1///|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
///|
/// Punycode encoding/decoding (RFC 3492)
/// Used for Internationalized Domain Names in Applications (IDNA)
///|
/// Error type for Punycode operations
pub(all) suberror PunycodeError {
Overflow
InvalidInput
BadInput
}
///|
pub extend PunycodeError with Show::{to_string, output}
///|
pub impl Show for PunycodeError with fn output(self, logger) {
match self {
Overflow => logger.write_string("Overflow")
InvalidInput => logger.write_string("InvalidInput")
BadInput => logger.write_string("BadInput")
}
}
// RFC 3492 constants (Section 4)
///|
/// Base for variable-length integer encoding. Punycode uses base-36
/// (letters a-z represent 0-25, digits 0-9 represent 26-35).
const Base : Int32 = 36
///|
/// Minimum threshold for variable-length integer encoding.
/// Ensures at least one digit is always output.
const Tmin : Int32 = 1
///|
/// Maximum threshold for variable-length integer encoding.
/// Equals the number of lowercase letters (a-z).
const Tmax : Int32 = 26
///|
/// Skew parameter for bias adaptation function.
/// Controls how quickly the bias adjusts to character frequencies.
const Skew : Int32 = 38
///|
/// Damping factor applied only to the first delta value.
/// Prevents the bias from changing too rapidly at the start.
const Damp : Int32 = 700
///|
/// Initial bias value for the adaptation algorithm.
/// Chosen to work well for typical internationalized domain names.
const InitialBias : Int32 = 72
///|
/// Initial value of n, the threshold between basic ASCII (0-127)
/// and non-basic code points that require encoding.
const InitialN : Int32 = 0x80
///|
/// Delimiter character separating the basic ASCII portion
/// from the Punycode-encoded portion in the output.
const Delimiter : Char = '-'
///|
/// Largest positive value representable by MoonBit's signed Int type.
const MaxInt : Int32 = 0x7FFFFFFF
///|
/// Bias adaptation function (RFC 3492 Section 3.4)
fn adapt(delta : Int32, numpoints : Int32, firsttime : Bool) -> Int32 {
let mut delta = delta
if firsttime {
delta = delta / Damp
} else {
delta = delta / 2
}
delta = delta + delta / numpoints
let mut k = 0
while delta > (Base - Tmin) * Tmax / 2 {
delta = delta / (Base - Tmin)
k = k + Base
}
k + (Base - Tmin + 1) * delta / (delta + Skew)
}
///|
/// Encode a digit to a basic code point (a-z for 0-25, 0-9 for 26-35)
fn encode_digit(d : Int32) -> Char {
if d < 26 {
(d + 'a'.to_int()).unsafe_to_char()
} else {
(d - 26 + '0'.to_int()).unsafe_to_char()
}
}
///|
/// Decode a basic code point to a digit
fn decode_digit(cp : Int32) -> Int32 {
if cp >= 'a'.to_int() && cp <= 'z'.to_int() {
cp - 'a'.to_int()
} else if cp >= 'A'.to_int() && cp <= 'Z'.to_int() {
cp - 'A'.to_int()
} else if cp >= '0'.to_int() && cp <= '9'.to_int() {
cp - '0'.to_int() + 26
} else {
Base // Invalid
}
}
///|
/// Whether every code point of `input` is basic. Code units below `InitialN`
/// are exactly the basic code points, as surrogates are above it.
fn is_basic(input : StringView) -> Bool {
for i in 0..<input.length() {
if input.unsafe_get(i).to_int() >= InitialN {
return false
}
}
true
}
///|
/// Encode a Unicode string to Punycode
pub fn encode(input : StringView) -> String raise PunycodeError {
if is_basic(input) {
// Only basic code points: they are copied, followed by the delimiter.
return if input.is_empty() {
""
} else if JsStrings {
// `to_owned` does not copy a view of a whole string.
input.to_owned() + "-"
} else {
basic_to_string(input)
}
}
// Reserve the input and a few digits for each code unit; the size hint
// counts bytes, two per UTF-16 code unit.
let output = StringBuilder(capacity=2 * (1 + 4 * input.length()))
ignore(encode_extended(input, output))
output.to_string()
}
///|
/// Encode a Unicode string to Punycode at the end of `output`, and return the
/// number of characters written, all of them ASCII.
///
/// When encoding fails, part of the encoding may already be in `output`.
pub fn encode_to(
input : StringView,
output : StringBuilder,
) -> Int32 raise PunycodeError {
if is_basic(input) {
// Only basic code points: they are copied, followed by the delimiter.
if input.is_empty() {
return 0
}
output.write_view(input)
output.write_char(Delimiter)
return input.length() + 1
}
encode_extended(input, output)
}
///|
/// Encode `input`, which holds at least one code point that is not basic, at
/// the end of `output`, and return the number of characters written.
fn encode_extended(
input : StringView,
output : StringBuilder,
) -> Int32 raise PunycodeError {
// The UTF-16 length bounds the number of code points.
let code_points : FixedArray[Int32] = FixedArray::make(input.length(), 0)
let mut count = 0
let mut basic_count = 0
for c in input {
let cp = c.to_int()
code_points[count] = cp
count = count + 1
if cp < InitialN {
basic_count = basic_count + 1
}
}
let mut written = 0
// Copy all basic code points to output
for i in 0..<count {
let cp = code_points[i]
if cp < InitialN {
output.write_char(cp.unsafe_to_char())
}
}
written = basic_count
// Add delimiter if there were basic characters
if basic_count > 0 {
output.write_char(Delimiter)
written = written + 1
}
let mut n = InitialN
let mut delta = 0
let mut bias = InitialBias
let mut handled = basic_count
while handled < count {
// Find the minimum code point >= n
let mut m = 0x10FFFF + 1
for i in 0..<count {
let cp = code_points[i]
if cp >= n && cp < m {
m = cp
}
}
// Increase delta enough to advance the decoder's <n,i> state to <m,0>
let code_point_step = m - n
let point_count = handled + 1
if code_point_step > (MaxInt - delta) / point_count {
raise Overflow
}
delta = delta + code_point_step * point_count
n = m
for i in 0..<count {
let cp = code_points[i]
if cp < n {
if delta == MaxInt {
raise Overflow
}
delta = delta + 1
} else if cp == n {
// Represent delta as a generalized variable-length integer
let mut q = delta
let mut k = Base
while true {
let t = if k <= bias {
Tmin
} else if k >= bias + Tmax {
Tmax
} else {
k - bias
}
if q < t {
break
}
output.write_char(encode_digit(t + (q - t) % (Base - t)))
written = written + 1
q = (q - t) / (Base - t)
k = k + Base
}
output.write_char(encode_digit(q))
written = written + 1
bias = adapt(delta, handled + 1, handled == basic_count)
delta = 0
handled = handled + 1
}
}
if delta == MaxInt {
raise Overflow
}
delta = delta + 1
n = n + 1
}
written
}
///|
/// Decode a Punycode string to Unicode
pub fn decode(input : StringView) -> String raise PunycodeError {
// Valid input is ASCII, so it is read as UTF-16 code units; any other
// unit is rejected where it is reached.
let length = input.length()
// Find the last delimiter
let mut basic_end = -1
for i = length - 1; i >= 0; i = i - 1 {
if input[i].to_int() == Delimiter.to_int() {
basic_end = i
break
}
}
// Code points of the output. Each one consumes at least one code unit of
// input, so the input length bounds their number.
let output : FixedArray[Int32] = FixedArray::make(length, 0)
let mut output_length = 0
// Copy basic code points before the last delimiter
for i in 0..<basic_end {
let unit = input[i].to_int()
if unit >= InitialN {
raise BadInput
}
output[i] = unit
output_length = i + 1
}
// Main decoding loop
let mut n = InitialN
let mut i_val = 0
let mut bias = InitialBias
let mut in_pos = if basic_end >= 0 { basic_end + 1 } else { 0 }
// UTF-16 length of the output
let mut output_units = output_length
while in_pos < length {
let oldi = i_val
let mut w = 1
let mut k = Base
while true {
if in_pos >= length {
raise BadInput
}
let digit = decode_digit(input[in_pos].to_int())
in_pos = in_pos + 1
if digit >= Base {
raise BadInput
}
if digit > (MaxInt - i_val) / w {
raise Overflow
}
i_val = i_val + digit * w
let t = if k <= bias {
Tmin
} else if k >= bias + Tmax {
Tmax
} else {
k - bias
}
if digit < t {
break
}
if w > MaxInt / (Base - t) {
raise Overflow
}
w = w * (Base - t)
k = k + Base
}
let out_len = output_length + 1
bias = adapt(i_val - oldi, out_len, oldi == 0)
if i_val / out_len > MaxInt - n {
raise Overflow
}
n = n + i_val / out_len
i_val = i_val % out_len
// Reject values that are not valid Unicode scalar values before building
// the output string. Int::to_char also rejects surrogate code points.
guard n.to_char() is Some(_) else { raise BadInput }
// Insert n at position i_val.
output.blit_to(
output,
len=output_length - i_val,
src_offset=i_val,
dst_offset=i_val + 1,
)
output[i_val] = n
output_length = out_len
output_units += if n > 0xFFFF { 2 } else { 1 }
i_val = i_val + 1
}
if JsStrings {
// The size hint counts bytes, so the builder is filled exactly.
let result = StringBuilder(capacity=2 * output_units)
for i in 0..<output_length {
result.write_char(output[i].unsafe_to_char())
}
return result.to_string()
}
code_points_to_string(output, output_length, output_units)
}
///|
/// Whether strings are JS strings. These are cheaper to build by appending, as
/// a string builder does, than from an array of code units. Elsewhere an array
/// of code units becomes a string without a copy, while a builder or a
/// concatenation allocates a buffer as well as the string.
#cfg(target="js")
const JsStrings : Bool = true
///|
#cfg(not(target="js"))
const JsStrings : Bool = false
///|
/// The basic code points of `input` followed by the delimiter, as a string
/// allocated once.
fn basic_to_string(input : StringView) -> String {
let length = input.length()
let units : FixedArray[UInt16] = FixedArray::make(length + 1, 0)
for i in 0..<length {
// SAFETY: `i` is below the length of both `input` and `units`.
units.unsafe_set(i, input.unsafe_get(i))
}
units.unsafe_set(length, Delimiter.to_int().to_uint16())
uint16_array_to_string(units)
}
///|
/// The string of the first `count` code points of `code_points`, which take
/// `units` UTF-16 code units. They are written into an array of that length,
/// which becomes the string without a copy.
fn code_points_to_string(
code_points : FixedArray[Int32],
count : Int32,
units : Int32,
) -> String {
let result : FixedArray[UInt16] = FixedArray::make(units, 0)
let mut index = 0
for i in 0..<count {
let code_point = code_points[i]
// SAFETY: `units` counts two units for each code point above U+FFFF and
// one for every other, so every index is in bounds.
if code_point > 0xFFFF {
let offset = code_point - 0x10000
result.unsafe_set(index, (0xD800 + (offset >> 10)).to_uint16())
result.unsafe_set(index + 1, (0xDC00 + (offset & 0x3FF)).to_uint16())
index += 2
} else {
result.unsafe_set(index, code_point.to_uint16())
index += 1
}
}
uint16_array_to_string(result)
}
///|
/// Take ownership of UTF-16 code units as a string of the same length.
fn uint16_array_to_string(units : FixedArray[UInt16]) -> String = "%string.unsafe_from_uint16_fixedarray"