SwiftでBootstring(Punycode)。

概要

SwiftでBootstringを実装してみました→GitHub。

Bootstringとは？

RFC 3492で定義されている文字列のエンコード/デコード方式。そのうち特定のパラメータで設定されたものをPunycodeと呼び、国際化ドメイン名(IDN; Internationalized Domain Name)で用いられます。

実装

具体的な実装はソースコードを参照してもらえれば…というよりは、基本的にRFCをみながら愚直にコードを書いていくほかないのです…。RFCには擬似コードもあるので、それをSwiftに変換していくだけです。
ちなみに、QiitaにはJavaScriptでPunycodeを実装された方の投稿もあるようです。

Swiftらしく…？

ただ、せっかくSwiftを使うのだから、どこかでSwiftらしさを出してみたくなるものです。というわけで、encodeの実装(Bootstring.encode(_ string:String) throws -> String)については、RFCの擬似コードとは変えてみることにしました。

encode(_:)の中身

まず、non-basicなスカラーを最初に抜き出し、その値とインデックス(文字列内の位置)を保持しておくことにします。そこで役に立つのがSwiftのtupleです：(code)

Bootstring.swift(抜粋)

let input:[UnicodeScalar] = Array(string.unicodeScalars)
var output:[UnicodeScalar] = []
var nonBasicScalars:[(scalar:UnicodeScalar, index:Int)] = []

for ii in 0..<input.count {
  let scalar = input[ii]
  if scalar.isBasicScalar(in:self) {
    output.append(scalar)
  } else {
    nonBasicScalars.append((scalar:scalar, index:ii))
  }
}

そして、のちのちdeltaを計算しやすいようにnonBasicScalarsをソートしてしまいます。ソート順としては、スカラー値の昇順を原則とし、スカラー値が同じ場合はインデックスの昇順とします：(code)

Bootstring.swift(抜粋)

nonBasicScalars.sort {
  if $0.scalar < $1.scalar { return true }
  else if $0.scalar > $1.scalar { return false }
  else { return $0.index < $1.index }
}

そして、エンコーディングのループは、RFCにある擬似コードのような文字列全体の走査ではなく、nonBasicScalarsを頭から順番に処理していくということにします：(code)

Bootstring.swift(抜粋)

for ii in 0..<nonBasicScalars.count {
  let info = nonBasicScalars[ii]
  let target: Int = Int(info.scalar.value)
  let targetIndex: Int = info.index
  let basis: Int = Int(((ii == 0) ? self.initialScalar : nonBasicScalars[ii - 1].scalar).value)
  let basisIndex: Int = (ii == 0) ? 0 : nonBasicScalars[ii - 1].index
  // ...

ループ内では、deltaの計算にクロージャを用いることでSwiftらしさを演出します：(code)

Bootstring.swift(抜粋)

var delta: Int = 0
let deltaIncreaser: (Int, Int, Int) throws -> Void = { (start, end, border) in
  for jj in start..<end {
    if Int(input[jj].value) < border || input[jj].isBasicScalar(in:self) {
      guard delta < Int.max else { throw BootstringError.overflow }
      delta += 1
    }
  }
}
if target == basis {
  try deltaIncreaser(basisIndex, targetIndex, target)
} else {
  if ii != 0 {
    try deltaIncreaser(basisIndex, input.count, basis)
    // one more
    guard delta < Int.max else { throw BootstringError.overflow }
    delta += 1
  }
  try deltaIncreaser(0, targetIndex, target)

  // adjustment
  let diff: Int = target - basis - ((ii == 0) ? 0 : 1)
  guard diff <= (Int.max - delta) / (numberOfHandledCodePoints + 1) else {
    throw BootstringError.overflow
  }
  delta += diff * (numberOfHandledCodePoints + 1)
}

一応、deltaとは何だということについてはWikipediaの説明がわかりやすいです：

Punycode のエンコーディング手順を、「bücher」がどのようにして「bcher-kva」と変換されるかを例にとって説明する。
(中略)
エンコーディング手順を理解するために、先にデコーダの動作を理解する必要がある。デコーダは2つの状態変数iとnを持つオートマトンである。iは文字列への挿入位置のインデックスで、その範囲は0（これは文字列の先頭への挿入を表す）から現在の文字列の長さ（文字列の末尾への挿入を表す）である。nは挿入されるべき文字のコードポイントである。
iは0から始まり、nは128（非ASCII文字の最初のコードポイント）から始まる。状態遷移は単調であり、遷移すると i が1だけ増加する。ただしiがすでに最大値の場合はnを1増加しiは0に戻る。各状態遷移の際、nで表されるコードポイントを文字列に挿入するか、挿入をスキップする。
デコーダが文字を挿入する前に、スキップすべき挿入可能位置がいくつあるかを数値化したものがエンコーダによって生成されるコード番号である。"ü"のコードポイントは252である。よって ü の字を文字列の1文字目の後ろに挿入するには、"bcher"の中に6か所ある挿入ポイントに、üより前にある124の非ASCII文字が挿入されるのをスキップし、さらに0文字目（つまり文字列の先頭）にüが挿入されるのをスキップする必要がある。したがって、デコーダには必要な1文字を挿入するために、(6 × 124) + 1 = 745 の挿入可能位置をスキップするよう伝える必要がある。

この説明に出てくる例において、745がdeltaです。

一つ前に挿入された文字のスカラー値と今から挿入すべき文字のスカラー値が同じ場合(上のコードでif target == basis { ... }の部分)は、一つ前に挿入された文字のインデックスと今から挿入すべき文字のインデックスの間にいくつ(basicなスカラーと挿入済みnon-basicなスカラーの)文字があるかをカウントすればよいだけということになります(nonBasicScalarsはソート済であるため)。

逆に一つ前に挿入された文字のスカラー値と今から挿入すべき文字のスカラー値が違う場合(上のコードのelse節)の時はちょっとメンドくさいです。基本的には、(スカラー値の差分)×(処理済み文字数)がdeltaになるのですが、(上記のWikipediaの説明における)オートマトンの保持するiとnの値によってはdeltaの値を適切に増加させないといけません。

このあとdeltaを可変長整数としての文字列へ変換する工程がありますが、それはRFCの擬似コード通りで実装しました。

出来上がり

あとは、あーだこーだコードを書いておけば、他のプログラムから

import Bootstring

print("MajiでKoiする5秒前".addingPunycodeEncoding!)
// -> MajiKoi5-783gue6qz075azm5e

print("3B-ww4c5e180e575a65lsy2b".removingPunycodeEncoding!)
// -> 3年B組金八先生

と利用できるようになります。

おわりに

Swiftらしさとはなんだという哲学的な問いに答えを出すためにBootstringをSwiftで実装してみた…というのは嘘ですが、他の言語で書かれたコードをSwiftに“翻訳”するのはいろいろと勉強になります。
ただ、(見た目上の)Swiftらしさを優先することで速度などパフォーマンス面が犠牲になってしまう可能性は否定できません。たとえば、今回のコードで言えば、nonBasicScalarsというtupleのArrayを用意するとメモリ使用量は増えるでしょうし、それをソートすることが速度面でどうなのかと言われるとなんとも言えません。
でも、Swiftは書いていて楽しいのです。「楽しくなければプログラミングじゃないじゃん」の精神が一番大切だと思うのです。