ククログ

Firefox ESR60でタイトルバーのウィンドウコントロールボタンが機能しなくなる事がある問題の回避方法

Firefox ESR60をWindows 7で使用していると、ウィンドウコントロール（タイトルバーの「最小化」「最大化」「閉じる」のボタン）が動作しなくなる、という現象に見舞われる場合があります。Firefoxの法人サポート業務の中でこの障害についてお問い合わせを頂き、調査した結果、Firefox自体の不具合である事が判明しました。

この問題は既にMozillaに報告済みで、Firefox 67以降のバージョンで修正済みですが、Firefox ESR60では修正されない予定となっています。この記事では、Firefox ESR60をお使いの方向けに暫定的な回避方法をご案内します。

問題の状況とその原因

この現象は、FirefoxのUIの設計に由来する物です。

一般的なWindowsアプリケーションは、タイトルバーなどを含めたウィンドウの枠そのものはWindowsに描画や制御を任せて、枠の内側だけでUIを提供します。それに対し、Firefoxのブラウザウィンドウでは、タイトルバー領域に食い込む形でタブを表示させるため、タイトルバーを含むウィンドウの枠まで含めた全体を自前で制御しています。そのため、タイトルバー領域に食い込む形でタブが表示されている場面では、Windowsが標準で提供しているウィンドウコントロールのボタンは実は使われておらず、それを真似る形で置かれた独自のUI要素で代用しています。

通常、これらの代用ボタンは他のUI要素よりも全面に表示されるため、タブなどの下に隠れる事はなく、ユーザーは見たままの位置にあるボタンをクリックできます。しかし、特定の条件下ではこれらの代用ボタンが他のUI要素の下に隠れてしまう形となり、ボタンをクリックできなくなってしまいます。

この問題が起こる条件は、以下の通りです。

• Windows 7で、Windows自体のテーマとして「Classic」テーマを使用している。
• ツールバー上の右クリックメニューから「メニューバー」にチェックを入れており、メニューバーが常時表示される状態になっている。
• ウィンドウがwindow.open()で開かれ、その際、メニューバーを非表示にするように指定された。

Windowsのテーマ設定とFireofxのツールバーの設定を整えた状態で、w3schools.comのwindow.oepn()の各種指定のサンプルを開き「Try it」ボタンをクリックしてみて下さい。実際に、ボタンが機能しないためウィンドウを閉じられなくなっている*1事を確認できるはずです。

問題が再現した時のFirefoxの内部状態を詳しく調査すると、Classicテーマにおいては、この状況下ではタブバーのz-index（重ね合わせの優先順位）が2になるのに対し、ウィンドウコントロールのz-indexは常に1になるために、タブバーがウィンドウコントロールの上に表示されてしまっている状態である*2という事が分かりました。

なお、ClassicテーマはWindows 7以前のバージョンでのみ使用できる機能で、Windows 10以降では使えません*3。そのため、この問題はWindows 10以降では再現しません。

回避方法

原因が分かれば対策は容易です。

最も単純な対策は、ユーザープロファイル内にchromeという名前でフォルダを作成し、以下の内容のファイルをuserChrome.cssの名前で設置するというものです。

@namescape url("http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul");

/* WindowsでClassicテーマが反映されている場合、 */
@media (-moz-windows-classic) {
  /* タイトルバーにタブを表示する設定で、フルスクリーン表示でない時は、 */
  #main-window[tabsintitlebar]:not([sizemode=fullscreen]) #titlebar-buttonbox {
    /* ウィンドウコントロールの重ね合わせ順位をタブバーよりも上にする */
    z-index: 3 !important;
  }
}

ただ、ユーザープロファイルの位置はFirefoxの実行環境ごとに異なる*4ため、管理者側でこの対応を全クライアントに反映するのは難しいです。クライアント数が多い場合は、Firefoxのインストール先のchromeやbrowser\chrome配下に置かれたCSSファイルを自動的に読み込むためのスクリプトをMCD用設定ファイルに組み込むなどの方法をとるのがおすすめです。

修正の状況

原因が判明した時点で、本件はFirefox本体の問題としてbugzilla.mozilla.orgに以下の通り報告しました。

• 1521692 - Unclickable window controls (minimize, maximize and close buttons) on a window opened via window.open() with "toolbar", without "menubar", when the menu bar is configured as always shown and running on Windows 7 with the Classic theme

また、調査を行った時期にちょうどFirefoxのタブバー・タイトルバー周りの実装の仕方が変化していたため、最新の開発版でも状況を確認した所、Firefox 65以降ではWindows 7でなくても同様の問題が起こり、しかも今度はそもそもウィンドウコントロールが表示されなくなってしまっているという、より酷い状況でした。そのため、そちらは別の問題として以下の通り報告しました。

• 1521688 - Missing window controls (minimize, maximize and close buttons) on a window opened via window.open() with "toolbar", without "menubar", when the menu bar is configured as always shown

Firefox ESR60およびFirefox 64以前での問題（本記事で解説している問題）については、Firefox 65でタブバーの設計が変わったために現象としては再現しなくなった事と、セキュリティに関わる問題ではない事から、修正はされないという決定がなされています。

Firefox 65以降での問題については、既に修正のためのパッチを提供し、Firefox 67以降のバージョンに取り込まれる事が確定しています。Firefox 65に対しては修正はバックポートされず、Firefox 66については特に誰も働きかけなければ修正は反映されないままとなる見込みです。

まとめ

以上、Firefoxの法人向け有償サポートの中で発覚したFirefoxの不具合について暫定的な回避方法をご案内しました。

当社のフリーソフトウェアサポート事業では、当社が開発した物ではないソフトウェア製品についても、不具合の原因究明、暫定的回避策のご提案、および（将来のバージョンでの修正のための）開発元へのフィードバックなどのサポートを有償にて行っております。Firefoxのようなデスクトップアプリケーションだけでなく、サーバー上で動作する各種ソフトウェアについても、フリーソフトウェアの運用でトラブルが発生していてお困りの企業のシステム管理担当者さまがいらっしゃいましたら、メールフォームよりご相談下さい。

ツイートする

フォローする

Web Crypto API で AES-CBC や AES-GCM の初期ベクトルをより安全に生成する

先日の Web Crypto API の基本的な使い方の解説（改訂済み）においては、説明を簡単にするために AES-GCM の初期ベクトルを乱数に基づいて生成しましたが、これはセキュリティの観点からはあまり好ましくありません。本記事では、Web Crypto API で AES-CBC や AES-GCM を用いて暗号化する場合の、より安全な初期ベクトルの生成方法について解説します。

望ましい初期ベクトルとは？

前の記事でも述べていますが、初期ベクトルについて簡単におさらいします。

共通鍵暗号のアルゴリズムである AES にはいくつかの「暗号モード」があり、中でも CBC や GCM といったモードでは、暗号化に際して初期ベクトルというパラメータが必要となっています。これは、データを暗号化する際に添加する無関係のデータのことで、それによって暗号文から元のデータを予測しにくくするという意味があります*1。他の暗号モードの CTR でも、カウンタの nonce 部分がこれと同様の役割を果たします。

暗号の仕様上は、初期ベクトルやnonce*2は一意である事が求められています。そのため、「ランダムなだけの値」を初期ベクトルに使うと困った事になります。

ここで一旦整理してますが、値が一意であるということと値がランダムであるという事は本質的に全く別の事です。

• 値が一意である＝値が重複しない事が保証されている。
• 値がランダム（乱雑）である＝値が予想できない、または極めて予想しにくい事が保証されている。

これらは相反する概念ではなく直交する概念なので、「一意で、且つランダムである」「一意でもないし、ランダムでもない」「一意だが、ランダムではない」「一意ではないが、ランダムである」という4つの組み合わせが理論上あり得ます。「ランダムな値」というと、直感的には「一意で、且つランダムである」という事を指していそうに思えますが、実際には「一意ではないが、ランダムである」という値もその範囲に入ってきます。

これを踏まえると、一意である事が求められる初期ベクトルに、ランダムであるというだけの「乱数」を使うのは、本来は間違いであるという事が言えます。前の記事の例では crypto.getRandomValues() を用いましたが、これもあくまで暗号論的に強度の高い疑似乱数*3であって、一意な値であることが保証されているわけではありません。確率は低いですが、生成された値が過去の値と偶然一致してしまうという可能性はあります。

実際、本当は怖いAES-GCMの話 - ぼちぼち日記という記事の中では、疑似乱数で初期ベクトルを大量に生成すると誕生日のパラドックス*4によって初期ベクトルが衝突するという事が述べられています。

その一方で、仕様によれば、初期ベクトルは「一意である」という事は求められているものの、「予測不能である」という事は求められていません。極端な話、重複さえしなければ、「単調増加するカウンタ」という極めて予測しやすい物であっても何ら問題ないという事です。実際、仕様の中でもカウンタが妥当な実装の例として挙げられているほどです。

一意な値というとUUIDがまず思い浮かびますが、UUIDは生成方法が妥当でないと値が衝突する可能性が（低いですが）あります。言語のライブラリによってはUUIDの生成が乱数ベースとなっていて、このような実装では、UUIDという名前なのに一意な結果を得られる事は残念ながら保証されていないという事になってしまいます。

しかし、UUIDが信用できない場合でも、単調増加型のカウンタなら確実に一意な結果を得られます。

// Uint32Arrayで一桁だけのカウンタを作成
let counter = new Uint32Array(1);

// カウントを足す
counter[0]++;

function incrementCount(counter) {
  // 桁ごとの計算
  const increment = column => {
    // 左端（最上位）の桁からの繰り上がりは無いので、桁あふれした事のみ返す
    if (column < 0)
      return true;
    // 指定された桁の値を1増やす
    const result = ++counter[column];
    // 最大値を超えていないのであれば、そこで終了
    if (result <= 255)
      return false;
    // 最大値を超えてしまった場合、その桁の値を0にリセット
    counter[column] = +0;
    // その後、繰り上がって1つ左（上位）の桁の値を1増やす（再帰）
    return increment(column - 1);
  };
  // 右端（最下位）の桁を1増やし、左端（最上位）の桁があふれたかどうかを判定
  const overflow = increment(counter.length - 1);
  // 左端（最上位）の桁が溢れた場合、全体を0にリセットする
  if (overflow)
    counter.fill(0);
  return counter;
}

const counter = new Uint8Array(4);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 0, 0 ]

incrementCount(counter);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 0, 1 ]

incrementCount(counter);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 0, 2 ]

incrementCount(counter);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 0, 255 ]

incrementCount(counter);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 1, 0 ]

incrementCount(counter);
console.log(counter);
// => Uint8Array(16) [ 0, 0, 1, 1 ]

固定部とカウンタから初期ベクトルを組み立てる形で AES-GCM を使う

GCMの仕様では初期ベクトルの望ましい作り方の例がいくつか挙げられており、その中には、初期ベクトルを「前半の固定部」と「後半の変動部」に分けるやり方があります。

この文書では、固定部分は「デバイスの種類」「暗号化対象のコンテキスト」などを表すために使えると書かれています。よって、固定部として「暗号化を行うアプリのインスタンス」ごとに生成した値を使い、変動部に先のカウンタの値を使えば、GCMの仕様を満たす暗号化可能だと言えます。

そこで、前の記事に記載した AES-GCM による暗号化の例を元にして、カウンタを併用して初期ベクトルを組み立てる例を実装してみる事にします。

まず暗号の鍵ですが、これは話を簡単にするため、指定したパスフレーズ（パスワード）の文字列からその都度生成する事にします。鍵を自動生成ストレージに保管したり自動生成したりする場合については前の記事をご参照下さい。

async function getKey(passphrase, salt = null) {
  passphrase = (new TextEncoder()).encode(passphrase);
  let digest = await crypto.subtle.digest({ name: 'SHA-256' }, passphrase);
  let keyMaterial = await crypto.subtle.importKey('raw', digest, { name: 'PBKDF2' }, false, ['deriveKey']);
  if (!salt)
    salt = crypto.getRandomValues(new Uint8Array(16));
  let key = await crypto.subtle.deriveKey(
    {
      name: 'PBKDF2',
      salt,
      iterations: 100000,
      hash: 'SHA-256'
    },
    keyMaterial,
    { name: 'AES-GCM', length: 256 },
    false,
    ['encrypt', 'decrypt']
  );
  return [key, salt];
}

次は初期ベクトルの組み立てです。固定部の生成は以下の要領です。ここでは、最終的に128bitの長さの初期ベクトルにする前提で、そのうちカウンタに使う32bitを除いた残り96bitを固定部の長さとしています。

function getFixedField() {
  // 作成済みの値を取得する。
  let value = localStorage.getItem('96bitIVFixedField');
  // あれば、それを返す。
  if (value)
    return Uint8Array.from(JSON.parse(value));

  // 無ければ、新しい値（長さ96bit）を作成して保存する。
  // 96bitをUint8Arrayで表すため、96 / 8 = 12が桁数となる。
  value = crypto.getRandomValues(new Uint8Array(12));
  localStorage.setItem('96bitIVFixedField', JSON.stringify(Array.from(value)));
  return value;
}

作成済みの値があればそれを使い、無ければ新たに生成する、という形にすると、固定部の値が各実行インスタンスの識別子を表す事になります。先に述べた通り、乱数から得られた値は一意な値であることが保証されないので、本来は望ましくないのですが、個々の初期ベクトルを毎回乱数で生成するよりは衝突の確率が低いという事で、ここでは乱数を使う事にしました。

初期ベクトルの変動部は、前述の実装によるカウントアップ処理を使った単純なカウンタ前述の説明の通り32bitのカウンタにします。

function getInvocationField() {
  // 前回の値を取得。
  let counter = localStorage.getItem('32bitLastCounter');
  if (counter) // あればそれを使う。
    counter = Uint32Array.from(JSON.parse(counter));
  else // 無ければ新しいカウンタ（長さ32bit）を生成する。
    counter = new Uint32Array(1); 

  counter[0]++; // 値を1増やす。

  // 結果を保存する。
  localStorage.setItem('32bitLastCounter', JSON.stringify(Array.from(counter)));
}

ここでも、作成済みの値があればそれを使い、無ければ新たに生成する、という形にしており、これによって値が各実行インスタンスごとに固有のカウンタとなります。同じ実行インスタンスにおいて動作する限りは、カウンタの値は一意です。

こうして用意できる固定部と変動部の値は、それぞれ長さが96bitと32bitあります。これらを単純に連結すれば、128bitの長さの初期ベクトルを生成する事ができます。

let fixedPart      = getFixedField();
let invocationPart = getInvocationField();

// 固定部と形式を揃えるため、Uint8Arrayに変換する。
invocationPart = new Uint8Array(invocationPart.buffer);

// 2つのTyped Arrayの各桁をスプレッド構文で並べて、
// 新しい配列を生成
let concated = [...fixedPart, ...invocationPart];
// その配列をTyped Arrayに変換
let iv = Uint8Array.from(concated);

暗号化の際は、このようにして毎回新しい初期ベクトルを生成するようにします。

async function encrypt(input, passphrase) {
  let [key, salt]    = await getKey(passphrase);
  // 初期ベクトルを生成する。
  let fixedPart      = getFixedField();
  let invocationPart = getInvocationField();
  let iv = Uint8Array.from([...fixedPart, ...new Uint8Array(invocationPart.buffer)]);
  let encryptedData = await crypto.subtle.encrypt(
    { name: 'AES-GCM', iv },
    key,
    (new TextEncoder()).encode(JSON.stringify(input))
  );
  encryptedData = Array.from(new Uint8Array(encryptedData), char => String.fromCharCode(char)).join('');
  return JSON.stringify([
    btoa(encryptedData),
    // 暗号化されたデータには、必ず初期ベクトルの
    // 変動部とパスワードのsaltを添付して返す。
    invocationPart[0],
    Array.from(salt)
  ]);
}

関数の戻り値に初期ベクトルの変動部が添付されているという点がポイントです。AES-GCM においては、初期ベクトルは秘密である必要はありません。一方、初期ベクトルは暗号化されたデータの復号時に必要となります。以上の理由から、初期ベクトルは原則として、暗号化されたデータに添付してワンセットで取り扱う事になります。（鍵をパスワードから生成する場合、パスワードのsaltも同様に扱う必要があります。この例では、saltも初期ベクトルと併せてデータに添付しています。）

復号処理では、添付された初期ベクトルの変動部を取り出して固定部と組み合わせる事で、完全な初期ベクトルを復元する、という操作を行います。

// 暗号化されたデータに添付された初期ベクトルの変動部とsaltを得る。
let [encryptedData, invocationPart, salt] = JSON.parse(encryptedResult);
// 固定部を得る。
let fixedPart = getFixedField();
// 変動部をUint32Arrayに戻す。
let invocationPartTypedArray = new Uint32Array(1);
invocationPartTypedArray[0] = invocationPart;
// 変動部をUint8Arrayに変換する。
invocationPart = new Uint8Array(invocationPartTypedArray.buffer);
// 2つのTyped Arrayを連結して、完全な初期ベクトルを得る。
let iv = Uint8Array.from([...fixedPart, ...invocationPart]);

実際の復号処理は以下のようになります。

async function decrypt(encryptedResult, passphrase) {
  // 復号処理は、初期ベクトルが添付されたデータのみを取り扱うものとする。
  let [encryptedData, invocationPart, salt] = JSON.parse(encryptedResult);
  let [key, _] = await getKey(passphrase, Uint8Array.from(salt));
  let invocationPartTypedArray = new Uint32Array(1);
  invocationPartTypedArray[0] = invocationPart;
  // 初期ベクトルを復元する。
  let iv = Uint8Array.from([...getFixedField(), ...(new Uint8Array(invocationPartTypedArray.buffer))]);
  encryptedData = atob(encryptedData);
  encryptedData = Uint8Array.from(encryptedData.split(''), char => char.charCodeAt(0));
  let decryptedData = await crypto.subtle.decrypt(
    { name: 'AES-GCM', iv },
    key,
    encryptedData
  );
  decryptedData = (new TextDecoder()).decode(new Uint8Array(decryptedData));
  return JSON.parse(decryptedData);
}

ところで、ここでなぜ初期ベクトル全体ではなく変動部だけを添付しているかを疑問に思う人もいるのではないでしょうか。前の記事の例のように初期ベクトル全体を添付しておけば、上記のような初期ベクトルの復元処理は不要になるはずです。

初期ベクトルの変動部だけを添付する理由は2つあります。1つ目は、初期ベクトルの固定部は毎回共通のため、そのまま添付すると冗長だからで、これについては特に説明の必要はないでしょう。

2つ目の理由は、より安全性を高めるためです。このように暗号化されたデータ単体では初期ベクトルの全体が揃わないようにしておくと、もし万が一暗号化されたデータを知られたとしても、復元に必要な情報が揃わないため、攻撃はより困難になります。AES-GCM において初期ベクトルは秘密である必要はありませんが、一部だけでも秘密にすればより堅牢な保護が可能になる、という事です。

以上のコードをまとめた物をGistに置いてあります。以下の要領で実行すると、暗号化・復号を行える事、および、暗号化の度にカウンタの値が増加して一意な初期ベクトルを得られている事を確認できます。

(async () => {
  let passphrase = '開けゴマ';


  // 単純な文字列の暗号化と復号

  let encrypted = await encrypt('王様の耳はロバの耳', passphrase);
  console.log(encrypted);
  // => '["KoYoXAWjY1lAheEZrHYwAkbOf4e/kr8wgbVEPwNEjTawg3HTLmvvuXOqNn+R",[1],[122,107,206,161,208,200,58,46,97,139,37,201,101,28,223,203]]'

  let decrypted = await decrypt(encrypted, passphrase);
  console.log(decrypted);
  // => '王様の耳はロバの耳'


  // 複雑なデータの暗号化と復号

  encrypted = await encrypt({ a: 0, b: 1, c: true, d: 'foobar' }, passphrase);
  console.log(encrypted);
  // => '["bkvTkQNfTfnP7uUirivktij4iy66pSbiBDYJ3uNChkIlDJPBdkJ4Tqbe98a+QSujoHME",[2],[107,20,195,6,38,82,99,190,182,19,152,93,139,186,235,69]]'

  decrypted = await decrypt(encrypted, passphrase);
  console.log(decrypted);
  // => Object { a: 0, b: 1, c: true, d: "foobar" }
})();

まとめ

以上、AES-GCM の仕様で求められる性質を満たす形で Web Crypto API を用いて安全な暗号化を行う手順を解説しました。

この記事で実装したサンプルは、前の記事の例よりも、妥当且つ堅牢な物となっています。Web Crypto APIを使ってローカルデータを暗号化してみようという方に参考にしていただければ幸いです。

ツイートする

フォローする

Webアプリや拡張機能（アドオン）で、Web Crypto APIを使ってローカルに保存されるデータを暗号化する

※注記：本文末尾の「公開鍵暗号ではなく共通鍵暗号を使う理由」の説明について、2019年1月30日午前0時から21時までの間の初出時に内容の誤りがありました。また、2019年1月30日午前0時から2月5日20時頃までの間において、本文中での AES-CTR による暗号化処理が、 nonce を適切に指定していないために脆弱な状態となっていました。お詫びして訂正致します。初出時の内容のみをご覧になっていた方は、お手数ですが訂正後の説明を改めてご参照下さい。

クリアコードで主にMozilla製品のサポート業務に従事している、結城です。

FirefoxやThunderbirdがSSL/TLSで通信する際は、通信内容は自動的に暗号化されます。その一方で、Cookieやローカルストレージ、IndexedDBなどに保存されるデータは、平文のままでユーザーの環境に保存される事が多く、必要な場合はアプリ側で内容を暗号化しなくてはなりません。こういった場面でJavaScriptから使える暗号化・復号のための汎用APIが、Web Crypto APIです。

ただ、Web Crypto APIでデータを暗号化するにはある程度の知識が必要になります。「encrypt() という関数に文字列と鍵を渡したらいい感じに暗号化されて、decrypt() という関数に暗号と鍵を渡したらいい感じに復号される」というような単純な話ではないため、全く前提知識がないと、そう気軽には使えません。

この記事では、Web Crypto APIを用いたローカルデータの暗号化の基本的な手順をご紹介します。

Web Crypto APIでの暗号化の基本

Web Crypto APIでは様々な暗号方式を使えますが、それぞれ適切な用途が決まっています。一般的な「データの暗号化と復号」という場面では、以下のいずれかの暗号方式を使うことになります。

• 共通鍵暗号
  • AES-CTR
  • AES-CBC
  • AES-GCM
• 公開鍵暗号
  • RSA-OAEP

AES や RSA というのが具体的な暗号アルゴリズムの名前で、CTR、CBC、GCM というのは暗号モードの名前です。諸々の理由から、アプリ内部でローカルに保存するデータを暗号化するという場面では、AES-CTR AES-GCM が最適と言えるでしょう（詳細は後で述べます）。

JavaScriptで書かれた実装において、暗号化したいデータは普通は文字列や配列、オブジェクトといった形式を取っていることでしょう。しかしながら、Web Crypto APIでこれらのプリミティブな値を直接暗号化する事はできません。Web Crypto APIでは基本的に、データを ArrayBuffer やTyped Arrayと呼ばれる、よりバイナリ形式に近いデータで取り扱います。そのため、これらのデータ型の概念をきちんと理解しておく必要があります。Blob, ArrayBuffer, Uint8Array, DataURI の変換という記事では、これらのデータ型の関係を図を交えて分かりやすく説明してくれていますので、Web Crypto APIを触る前にぜひ読んでおきましょう。

また、Web Crypto APIの多くの機能は非同期処理になっており、処理結果がPromiseとして得られる場合が多いです。Promiseとは、簡単に言えば以下のような物です。

• Promiseは値の入れ物と言える。
  • 中の値を取り出すには、promise.then(function(value) { ... }) のように、then メソッドにコールバック関数を渡してその中で受け取る必要がある。
  • 中の値をすぐに取り出せるとは限らない。通信先のサーバーから結果が返ってきて初めて then メソッドのコールバック関数が呼ばれる、というような事もある。
• async function() { ... } という風に async キーワードを付けて定義された関数は、非同期の関数になる。
  • 非同期の関数を呼び出すと、関数の中で return した値は、呼び出した側からは常にPromiseとして受け取る事になる（関数の戻り値が常にPromiseになる）。
  • 非同期の関数の中では、let value = await promise; のように書くと、その場でPromiseの中の値を取り出せる（then メソッドを使わなくてもよくなる）。

以上の事を踏まえ、実際にデータを暗号化してみることにしましょう。

なお、Web Crypto APIの入出力はPromiseになっている事が多いので、以降のサンプルはすべて以下のような非同期関数の中で実行するものとします。

(async function() {

  // ここで実行

})();

鍵の生成

Web Crypto APIでの暗号化・復号では、Web Crypto APIで生成された CryptoKey クラスのインスタンスを鍵に使います。ここでは以下の2パターンの鍵の作り方を紹介します。

• ユーザーが入力したパスワードを鍵に変換する方法
• 完全に自動で鍵を生成する方法

パスワードを鍵に変換する

パスワードで保護されたOffice文書やPDFを取り扱う時のように、暗号化や復号の時にユーザーによるパスワードの入力を求める形にしたい場合には、入力されたパスワードを CryptoKey クラスのインスタンスに変換する操作を行います。Webブラウザで開発者用のコンソールを開いて、以下のスクリプトを実行してみると、実際に得られた AES-GCM 用の鍵がコンソールに出力されます。

// パスワードとして使う文字列。（ユーザーの入力を受け付ける）
let password = prompt('パスワードを入力して下さい'); // 例：'開けゴマ'

// 文字列をTyped Arrayに変換する。
let passwordUint8Array = (new TextEncoder()).encode(password);

// パスワードのハッシュ値を計算する。
let digest = await crypto.subtle.digest(
  // ハッシュ値の計算に用いるアルゴリズム。
  { name: 'SHA-256' },
  passwordUint8Array
);

// 生パスワードからのハッシュ値から、salt付きでハッシュ化するための素材を得る
let keyMaterial = await crypto.subtle.importKey(
  'raw',
  digest,
  { name: 'PBKDF2' },
  // 鍵のエクスポートを許可するかどうかの指定。falseでエクスポートを禁止する。
  false,
  // 鍵の用途。ここでは、「鍵の変換に使う」と指定している。
  ['deriveKey']
);

// 乱数でsaltを作成する。
let salt = crypto.getRandomValues(new Uint8Array(16));

// 素材にsaltを付与して、最終的なWeb Crypto API用の鍵に変換する。
let secretKey = await  crypto.subtle.deriveKey(
  {
    name: 'PBKDF2',
    salt,
    iterations: 100000, // ストレッチングの回数。
    hash: 'SHA-256'
  },
  keyMaterial,
  // アルゴリズム。
  { name: 'AES-GCM', length: 256 },
  // 鍵のエクスポートを禁止する。
  false,
  // 鍵の用途は、「データの暗号化と復号に使う」と指定。
  ['encrypt', 'decrypt']
);

console.log(secretKey);
// => CryptoKey { type: "secret", extractable: false, algorithm: {…}, usages: (2) […] }

この使い方においては、CryptoKey クラスのインスタンスとして得られた鍵はメモリ上に一時的に保持しておくだけでよく、ログアウト時やアプリの終了時にはそのまま破棄する事になります。次回訪問時・ログイン時・アプリ起動時には、再びパスワードの入力を求め、その都度この方法で鍵へと変換します。

// saltの保存。
localStorage.setItem('passwordSalt',
  JSON.stringify(Array.from(salt)));

// saltの復元。
let salt = localStorage.getItem('passwordSalt');
salt = Uint8Array.from(JSON.parse(salt));

鍵の自動生成

「何らかの方法で鍵を安全な場所（暗号化したデータとは別の保存先）に保管できる」という前提がある場合には、crypto.subtle.generateKey() を使って鍵を生成し、ユーザーにパスワードの入力を求めずに暗黙的に暗号化・復号を行うという事もできます。この場合、鍵は以下のように生成します。

let secretKey = await crypto.subtle.generateKey(
  // アルゴリズムと鍵長。ここでは最長の256bitを指定している。
  { name: 'AES-GCM', length: 256 },
  // 鍵のエクスポートを許可するかどうか。trueでエクスポートを許可する。
  true,
  // 鍵の用途。
  ['encrypt', 'decrypt']
);
console.log(secretKey);
// => CryptoKey { type: 'secret', extractable: true, algorithm: Object, usages: Array[2] }

生成された鍵は CryptoKey クラスのインスタンスとなっており、そのままでは永続化（保存）できませんが、以下のようにすると、JSON Web Key形式（通常のオブジェクト）として鍵をエクスポートできます。

// JSON Web Key（JWK）形式でのエクスポート。
let exportedSecretKey = await crypto.subtle.exportKey('jwk', secretKey);
console.log(exportedSecretKey);
// => Object { alg: "A256GCM", ext: true, k: "DAvha1Scb8jTqk1KUTQlMRdffegdam0AylWRbQTOOfc", key_ops: (2) […], kty: "oct" }

このようにして得られたJWK形式の鍵は、以下の手順で再び CryptoKey のインスタンスに戻す事ができます。

// JWK形式からのインポート。
let importedSecretKey = await crypto.subtle.importKey(
  'jwk',
  exportedSecretKey,
  // 鍵を生成した際の暗号アルゴリズム。
  { name: 'AES-GCM' },
  // 再エクスポートを許可するかどうかの指定。falseでエクスポートを禁止する。
  false,
  // 鍵の用途。
  ['encrypt', 'decrypt']
);
console.log(importedSecretKey);
// => CryptoKey { type: 'secret', extractable: true, algorithm: Object, usages: Array[2] }

実際には、初回訪問時・初回起動時などのタイミングで生成した鍵をエクスポートして安全な場所に補完しておき、次回訪問時・次回起動時などのタイミングでそれを読み取ってインポートし、メモリ上に鍵を復元する、といった要領で使う事になります。

データの暗号化

鍵の準備ができたらいよいよ本題の暗号化ですが、その前に、「暗号化する対象のデータ」を「暗号化できるデータ形式」に変換するという操作が必要です。

Web Crypto APIの暗号化処理は、データの入出力を ArrayBuffer やTyped Arrayの形式のみで行う仕様になっているため、どんなデータを暗号化するにせよ、何らかの方法でデータをこれらの形式に変換しなくてはなりません。文字列は 前出の例の中で行っていたように、TextEncoder を使って以下のようにTyped Arrayに変換できます。

// データをTyped Arrayに変換。
let inputData = (new TextEncoder()).encode('暗号化したい文字列');
console.log(inputData);
// => Uint8Array(27) [ 230, 154, 151, 229, 143, 183, 229, 140, 150, 227, … ]

オブジェクト形式のデータであれば、この直前に「JSON.stringify() で文字列に変換する」という操作を加えればよいでしょう。

入力データが用意できたら、次は初期ベクトルの準備です。

初期ベクトルとは、AES-CBC および AES-GCM においてデータを同じ鍵で暗号化する際に、暗号文から内容の推測を困難にするために付与する値です*2。パスワードのハッシュ化に用いるsaltのようなもの、と言えば分かりやすいでしょうか。本来は一意な値である必要がありますが、ここでは話を単純にするために、とりあえず乱数を使う事にします。実際に使う時は、きちんとした初期ベクトルを生成する手順の解説も併せて参照して下さい。

// 初期ベクトルとして、8bit * 16桁 = 128bit分の領域を確保し、乱数で埋める。
let iv = crypto.getRandomValues(new Uint8Array(16));

入力データと初期ベクトルが用意できたら、ようやく暗号化です。これは以下の要領で行います。

let encryptedArrayBuffer = await crypto.subtle.encrypt(
  // 暗号アルゴリズムの指定とパラメータ。
  { name: 'AES-GCM',
    iv },
  // 事前に用意しておいた鍵。
  secretKey,
  // ArrayBufferまたはTyped Arrayに変換した入力データ。
  inputData
);
console.log(encryptedArrayBuffer);
// => ArrayBuffer { byteLength: 27 }

暗号化後のデータは、非同期に ArrayBuffer 形式で返されます。ここでは27バイトの長さがあるという事だけが分かっているため、このような表示になっています。

データを暗号化できたら、今度はこれをIndexedDBや localStorage などに格納可能な形式に変換します。例えば文字列への変換であれば、以下の手順で行えます。

let encryptedBytes = Array.from(new Uint8Array(encryptedArrayBuffer), char => String.fromCharCode(char)).join('');
console.log(encryptedBytes);
// => �����`Ù�¥ë�`û-Þm#þ'�¾��[�·�

ここでは ArrayBuffer 形式で27バイトの長さのデータとして得られた物を、8bitずつに切り分けて Unit8Array に変換し、さらにその1バイトずつを文字コードと見なして文字に変換しています。

このような文字列はBinary Stringと呼ばれ、コンソールなどに出力しても文字化けした結果になる事がほとんどのため、データを持ち回る過程で破損してしまわないよう、取り扱いには注意が必要です。安全のためには、以下のようにしてBase64エンコード済みの文字列に変換して、文字化けなどが起こりにくい安全な状態で取り回すのがお薦めです。

let encryptedBase64String = btoa(encryptedBytes);
console.log(encryptedBase64String);
// => YPgdHZgguUeHpt9FcYy2IaZTfbTNswbfn93e

AES-GCMで暗号化したデータ*3の復号には、暗号化時に使用した初期ベクトルが必要となります*4。以下のようにして、暗号化したデータとセットで保存しておきます。

localStorage.setItem('encryptedData',
  JSON.stringify({
    data: encryptedBase64String,
    iv:   Array.from(iv)
  }));

データの復号

次は、暗号化済みのデータから元のデータを取り出してみましょう。

Web Crypto APIの復号処理も、暗号化処理と同様、データの入出力を ArrayBuffer やTyped Arrayの形式のみで行う仕様になっています。先の例と逆の操作を行い、まずは暗号化されたデータを ArrayBuffer またはTyped Array形式に変換します。

let encryptedData = JSON.parse(localStorage.getItem('encryptedData'));
let encryptedBase64String = encryptedData.data;
// 通常のArrayとして保存しておいた初期ベクトルをUint8Arrayに戻す
let iv = Uint8Array.from(encryptedData.iv);

// Base64エンコードされた文字列→Binary String
let encryptedBytes = atob(encryptedBase64String);

// Binary String→Typed Array
let encryptedData = Uint8Array.from(encryptedBytes.split(''), char => char.charCodeAt(0));

データの準備ができたら、いよいよ復号です。これは以下の手順で行います。

let decryptedArrayBuffer = await crypto.subtle.decrypt(
  // 暗号アルゴリズムの指定とパラメータ。暗号化時と同じ内容を指定する。
  { name: 'AES-GCM',
    iv },
  // 暗号化の際に使用した物と同じ鍵。
  secretKey,
  // ArrayBufferまたはTyped Arrayに変換した暗号化済みデータ。
  encryptedData
);
console.log(decryptedArrayBuffer);
// => ArrayBuffer { byteLength: 27 }

復号の時には、暗号化時と同じパラメータ、同じ鍵が必要である点に注意して下さい。何らかのトラブルで鍵や初期ベクトルを喪失してしまうと、元のデータは永遠に取り出せなくなってしまいます。

復号されたデータは ArrayBuffer 形式になっています。これを通常の文字列へ変換するには以下のように操作します。

let decryptedString = (new TextDecoder()).decode(new Uint8Array(decryptedArrayBuffer));
console.log(decryptedString);
// => '暗号化したい文字列'

無事に、暗号化する前の平文であった「暗号化したい文字列」という文字列を取り出す事ができました。

疑問

なぜ暗号アルゴリズムに AES-CTR AES-GCM を使うのか？

冒頭で、Web Crypto APIでデータの暗号化と復号に使えるアルゴリズムは4つあると述べましたが、本記事ではその中で何故 AES-CTR AES-GCM を選択しているのかについて、疑問に思う人もいるでしょう。

暗号アルゴリズムには、大別して「共通鍵暗号」と「公開鍵暗号」の2種類があります。共通鍵暗号は暗号化と復号に同じ鍵を使う方式、公開鍵暗号は暗号化と復号で異なる鍵を使う方式です。公開鍵暗号は「暗号化したデータと、それを復号する鍵の両方を、信頼できない通信経路で送り、受信側で復号する」「暗号化と復号を別々の所で（別々の人が）行う」という場面に適しています。逆に言うと、「アプリ内部でローカルに保存するデータを暗号化する」という場面のように、データや鍵が信頼できない通信経路を通る事がないのであれば暗号化も復号も同じ所で行うのであれば、公開鍵暗号（RSA-OAEP）ではなく共通鍵暗号（AES-* 系）で充分に安全だと言えます。

また、AES-* 系の中で AES-CTR を選択する理由は、他の2つが「初期ベクトル」という、鍵とは別の使い捨ての情報を組み合わせて使う（「鍵」と「初期ベクトル」の両方が揃って初めて暗号を復号できる）方式だからです。

AES-CBC と AES-GCM は、1回1回の暗号化・復号ごとに初期ベクトルを変えることで安全性を高める前提の方式です。ネットワークを通じてサーバーとクライアントの間でデータをやりとりするという場面では、暗号化して送られたデータはすぐに受け手の側で復号されます。このようなケースでは、同じ暗号データを何度も復号するという事は起こり得ないため、初期ベクトルは使い捨てにできます。

一方、アプリケーションのローカルデータを暗号化するという場面では、暗号化して保存されたデータを何度も復号する必要があります。データの復号には暗号化した時と同じ初期ベクトルが必要になるため、必然的に、初期ベクトルは使い捨てにできず、何度も使い回す事になります。本当は怖いAES-GCMの話 - ぼちぼち日記などの解説記事で詳しく述べられていますが、初期ベクトルを使い回した場合これらの暗号アルゴリズムは非常に脆弱な物となり、「情報の漏洩を防ぐ」という目的を達成できなくなってしまいます。

以上の理由から、このような場面では初期ベクトルを用いない方式である AES-CTR が最適だと言える訳です。

AES-* 系の中で AES-GCM を選択した理由は、他の2つには以下のようなデメリットがあるからです。

• AES-CTR: カウンタの取り扱いが初期ベクトルに比べて面倒。
• AES-CBC: 暗号化の並列処理ができない＝暗号化処理に時間がかかる可能性がある。

Webアプリなどでパスワード認証を実装する際には、パスワードをそのまま保存するのはなく、非可逆的に変換した結果であるハッシュ値を保存する事が一般に推奨されています。この時には、ハッシュ値から元のパスワードを推測しにくくするために、パスワードに余計なデータを加えてからハッシュ化するのが一般的です。この追加するデータを「塩をまぶす」ことに例えてsaltと呼びます。

これと同様にAESにおいても、データには必ずsaltのような一意なデータを付与してから暗号化するようになっています。これは仕様上秘密である必要はなく、一意でさえあればいいという事になっています。AES-CBC および AES-GCM では、そのようなsalt相当のデータを「初期ベクトル」と呼んでいます。

一方、AES-CTR ではsaltにあたるデータを「カウンタ」の一部として与えます。カウンタは最大で16byte＝128bitの長さを指定できますが、そのうち一部をnonce（一意な数字）、残りを0からカウントアップする文字通りのカウンタとして使う事になっています。例えば128bit中の64bitをnonce、残り64bitをカウントアップ部にする、といった要領です。……という具合に長々説明している事自体に顕れていますが、「一意な値を1つ用意するだけでいい」という初期ベクトルに比べて、カウンタは取り扱いが若干ややこしいという事自体が AES-CTR のデメリットと言えます。

では、AES-CTR 以外なら AES-CBC でも AES-GCM でもどちらでも良いのでは？ という話になりそうですが、AES-CBC には処理を並列化できないという原理上の制限があります。AES-CTR や AES-GCM にはそのような制限が無く、上手く実装されたソフトウェアであれば、マルチスレッドを活用した並列処理で高速ができます*5。

以上の理由から、この3つの選択肢の中では総合的に見て AES-GCM が最もメリットが大きいと筆者は考えています。

なお、本文中の例のように乱数を使って初期ベクトルを生成するのは、本来は望ましい事ではありません。実際の実装にそのまま組み込む前には、よりセキュアなきちんとした初期ベクトルを生成する手順の解説も併せてご参照下さい。

自動生成した鍵はどこに保存すればよいのか？

鍵を自動生成して暗黙的に暗号化・復号を行うという動作をさせたい場合、鍵は暗号化されたデータとは別の安全な場所に置く必要があります。生の鍵を暗号化されたデータと同じ場所に保存してしまっては、暗号化の意味がありません

鍵の置き場所としては、例えば以下のような例が考えられます。

• ファイルとして保存した物をUSBメモリに書き込み、そのUSBメモリを物理的な鍵として使う。
• QRコードに変換して表示した物をスマートフォンで撮影し、そのスマートフォンを物理的な鍵として使う。
• 鍵をICカードに保存し、その都度鍵をICカードリーダー経由で読み取る事として、ICカードそのものを物理的な鍵として使う。
• パスワードマネージャの中にパスワードの一種として保管し、パスワードマネージャのマスターパスワードで保護する。

こういった方法で鍵を保存しておくやり方と、都度パスワードの入力を求めるやり方のどちらが安全かについては、専門家の間でも意見が分かれているようです。鍵をデバイス上に保存しておくやり方には、当然ながら、デバイスそのものが盗難された場合にデータを保護できなくなるというリスクがあります。一方で、パスワード入力を頻繁に求める方法は、パスワードの入力の機会が増えるため、キーロガーやショルダーハッキングといった攻撃に遭うリスクが増大します。パスワードマネージャとマスターパスワードを使う方法は、両者の弱点を補うものと言えます。

まとめ

以上、Web Crypto APIを使ってJavaScriptでローカルデータを暗号化する手順をご紹介しました。個人情報のようにクリティカルな情報を取り扱うWebアプリや拡張機能を開発する場合に、参考にしてみて下さい。

ツイートする

フォローする

Gecko Embedded: 60ESR対応のフィードバック

60ESR対応フィードバックの顛末

クリアコードでは Gecko（Firefox）を組み込み機器向けに移植する取り組みを行っています。

• Gecko Embedded ESR60

この対応にあたっては OSSystems/meta-browser というYoctoレイヤをフォークして作業を行っていますが、対応が落ちついたバージョンについてはアップストリーム（OSSystems/meta-browser）に成果をフィードバックしています。例えば52ESRへのメジャーバージョンアップの対応はクリアコードの成果が元となっています。

さて、60ESRへのメジャーバージョンアップ対応についてもフィードバックをしていたのですが、最後まで自分たちでは解決できなかった問題が一つありました。今回は、OSSにはこんなフィードバックの仕方もあるのだという事例として紹介したいと思います。

meta-rustへの依存

52ESRから60ESRへの更新にあたって一番大きな問題となったのが、Firefox本体にRustで書かれたコードが導入された点です。通常、Firefoxをビルドする際にはrustupというコマンドでツールチェーンを導入します。クリアコードで60ESRのYoctoへのポーティングを開始した当初も、Rustのツールチェーンについてはrustupで導入したものを使用していました。

しかし、Yoctoでは一貫したクロスビルド環境を提供するために、ツールチェーン類も全てYoctoでビルドするのが基本です。このため、RustのツールチェーンについてもYoctoでビルドした物を使う方がよりYoctoらしいと言えます。調べてみたところ、既にmeta-rustというYoctoレイヤが存在していることが分かりましたので、これを利用することとしました。

ターゲット環境用のlibstd-rsを参照できない問題

meta-rustへの対応作業を進めていく中で、Firefoxのビルドシステムがターゲット環境用のlibstd-rsを発見してくれないという問題に遭遇しました。しかし、我々はRustのビルドの仕組みには不慣れであったため、それがどこの問題であるかをはっきりと切り分けることができていませんでした。一方で、meta-rustでのビルドの際に、libstd-rsのみビルド済みのものを導入することで、ひとまずこの問題を突破できることが分かりました。

• https://github.com/meta-rust/meta-rust/pull/191
• https://github.com/meta-rust/meta-rust/pull/208

その他発生していた問題については解決することができ、Firefoxのビルドが全て通るところまでは到達しました。

上記の回避策が正しい修正方法ではないということは分かっていたのですが、ではどこでどう修正をするのが正しいのかという点については、少し調査をしてみた限りでは判断がつかない状態でした。時間をかければいずれは解明できるのは間違いないのですが、我々には他にも取り組まなければいけない問題が山積していたため、その時点では、これ以上時間をかけることはできませんでした。

ひとまずOSSystems/meta-browserに対しては「こういう問題があってまだ調査中だから、マージするのはもうちょっと待ってね」という形でpull requestを投げておきました。

• https://github.com/OSSystems/meta-browser/pull/160

未解決のままマージされる

ところがしばらくすると、 Yocto/Open EmbeddedプロジェクトのKhem Raj氏が、OSSystems/meta-browserのメンテナであるOtavio Salvador氏に働きかけ、上記のlibstd-rsの問題が未解決であるにも関わらず、このpull requestをmasterにマージしてしまいました。上記の回避策はmeta-rustにはマージされていませんので、そのままではビルドを通すことすらできません。私の目から見るとちょっとした暴挙にも見えたのですが、状況についてはKhem Raj氏にも間違いなく伝わっているので、何か算段があるのだろうということでしばらく経過を見守ることにしました。

あとから分かったのですが、ちょうどYoctoの次のリリース向けの開発が始まるタイミングであったため、とりあえずmasterにマージしてCIに組み込んでしまってからの方が問題に取り組みやすいという事情があったようです。しばらく時間はかかりましたが、無事Khem Raj氏から問題を解決するpull requestが投げられました。

• https://github.com/OSSystems/meta-browser/pull/202

我々の方ではmeta-rustとmeta-browserのどちらで対処すべき問題なのかすら切り分けることができていませんでしたが、meta-browserで対処すべき問題だったようです。

本事例の感想

今回の件については、以下のような懸念から、ともすればフィードバックを躊躇してしまいがちな事例ではないかと思います。

• このような中途半端なpull requestを送ると、アップストリームの開発者から罵倒されたりはしないか?
• 「この程度の問題すら自分たちで解決できていない」ということを晒すことになるので、恥ずかしいなぁ。

前者については、確かにプロジェクトによってはそのようなpull requestが歓迎されないこともあるでしょう。とはいえ、今回の事例についてはそこそこ工数がかかる60ESRポーティング作業を粗方済ませており、その成果が有益と感じる開発者も多いはずです。また、後者については「聞くのは一時の恥、聞かぬは一生の恥」の良い事例ではないかと思います。結果的にはアップストリームの開発者の協力を得て問題を解決することもできて、成果をより多くの人に使ってもらえる状態にできたので、中途半端でもフィードバックをしておいて良かったなと感じています。

皆さんも「この程度のものは誰の役にも立たないだろう」「この程度のものを世に出すのは恥ずかしい」などと一人で勝手に思い込まないで、手元にある成果を積極的に公開してみてはいかがでしょうか？ひょっとすると、それが世界のどこかで悩んでいる開発者の問題を解決して、感謝してもらえるかもしれませんよ。

ツイートする

フォローする

階層構造データ用のGroongaのスキーマ設計方法

Groongaを開発している須藤です。

GroongaにはRDBMS（MySQLやMariaDBやPostgreSQLなど）と同じようにテーブルとカラムがあり、それらに構造化したデータを保存します。しかし、用途が違う（Groongaは検索がメインでRDBMSは検索だけでなくデータの管理も大事）のでスキーマの設計方法はRDBMSでの設計方法と違う部分があります。そのため、RDBMSのスキーマの設計に慣れている人でもGroongaのスキーマをうまく設計できないことがあります。

この記事では少し複雑なデータをGroongaで検索するためのスキーマの設計方法を説明します。

なお、ここで使っている設計を実装したGroongaコマンドはgroonga/groonga-schema-design-exampleにあります。実際に試してみると理解が深まるはずなのでぜひ試してみてください。

データ

まず、検索対象のデータを説明します。

検索対象は次の2つです。

• 論文
• 書籍

それぞれのデータがもつ情報は同じものもあれば違うものもあります。

たとえば、「タイトル」は「論文」にも「書籍」にもあります。

しかし、「雑誌」は「論文」だけにあり、「書籍」にはありません。（論文が収録されている雑誌の情報です。）

また、次のような親子関係があります。「論文」はいくつも階層になった親があります。書籍は複数の親を持ちます。少し複雑なデータですね！

• 出版元

  • 雑誌
    • 号
      • 論文

• 出版社

  • 書籍

• 親カテゴリー

  • 子カテゴリー
    • 書籍

• シリーズ

  • 書籍（シリーズに属さない書籍もある）

検索方法

この少し複雑なデータに対して次のような検索をするためのスキーマを設計します。

• 「論文」と「書籍」を横断全文検索
• 複数カラムで横断全文検索
  • たとえば「タイトル」と「著者」で横断全文検索
• 「論文」だけを全文検索
• 「書籍」だけを全文検索
• 検索結果を任意の親でドリルダウン
  • たとえば「出版元」でドリルダウン
• 指定した親に属する子レコードを検索
  • たとえば「出版元」が発行している「雑誌」を検索

設計の概要

Groongaでは検索対象を1つのテーブルに集めることが重要です。すごく重要です。本当に重要です。

今回のケースでは「論文」と「書籍」が検索対象なので、それらを同じテーブルに格納します。今回の設計では2つ合わせて「文献」と扱うことにし、Literatureテーブルを作成します。

Literatureテーブルの定義は次の通りです。

table_create Literature TABLE_HASH_KEY ShortText

主キーに設定する値は「論文」と「書籍」全体で一意にする必要があることに注意してください。「論文」ではISSNとなにかを使って、「書籍」ではISBNを使うと一意にできる気がします。ここでは、どうにかして一意にできる前提で設計を進めます。

LiteratureでTABLE_HASH_KEYを使っているのは、今回のケースでは主キーで完全一致検索できれば十分だからです。

参考：TABLE_*の特徴の違い

「論文」と「書籍」を同じテーブルに入れるため、区別するための情報も格納します。この設計ではtypeカラムを追加し、そこに"paper"（「論文」）または"book"（「書籍」）を格納することにします。

typeの型はShortTextでもよいのですが、検索効率および空間効率を考慮してTypes型にします。Typesはこの後にすぐ定義しますが、ただのテーブルです。カラムの型にテーブルを指定すると実際のデータ（"paper"と"book"）はTypesテーブルの主キーに入ります。カラムにはTypesテーブルの該当レコードのID（1と2とか）が入ります。各カラムに入るデータは単なる数値なので比較も高速（検索効率がよい）ですし、サイズも小さい（空間効率がよい）です。

column_create Literature type COLUMN_SCALAR Types

Typesは次のように定義したテーブルです。主キーには"paper"または"book"を設定します。主キーは完全一致だけできれば十分なのでTABLE_HASH_KEYにしています。

# "paper"または"book"
table_create Types TABLE_HASH_KEY ShortText

Literatureテーブルにレコードを追加したときにこのテーブルにも自動でレコードが追加されるので明示的に管理する必要はありません。typeカラムに"paper"を格納しようとすれば自動でTypesテーブルに主キーが"paper"のレコードが追加されます。すでにレコードがあればそのレコードを使います。つまり、typeカラムの型にShortTextを使ったときと同じように使えます。

型にテーブルを指定する方法はGroongaではよく使う方法です。用途はいろいろありますが、この使い方はRDBMSでいうenum型のようなものを実現するための使い方です。enum型のように値を制限することはできませんが。。。他の用途は後ででてきます。

Literatureに「論文」と「書籍」の情報をすべて格納します。中には「論文」にしかない情報あるいは「書籍」にしかない情報も存在します。存在しない情報は該当カラムに値を設定しません。

たとえば、「子カテゴリー」情報は「書籍」にしか存在しないので「論文」用のレコードを格納するときは「子カテゴリー」情報のカラムに値を設定しません。

GroongaにはNULLはないので、値を設定しなかったカラムの値はその型の初期値になっています。たとえば、ShortTextなら空文字列ですし、Int32なら0です。

今回の設計ではLiteratureテーブルには次のカラムを用意します。

• type (Types): 種類（「論文」（"paper"）か「書籍」（"book"））
• title (ShortText): タイトル
• authors (Authors): 著者（複数）
• volume (Volumes): 号（「論文」のみ）
• book_publisher (BookPublishers): 出版社（「書籍」のみ）
• child_category (ChildCategories): 子カテゴリー（「書籍」のみ）
• series (Series): シリーズ（「書籍」のみ）

titleとauthorsは全文検索のためのカラムです。

検索項目を増やす場合は単にカラムを増やしてインデックスを追加するだけです。追加方法はauthorsを例にして後述します。全文検索用のスキーマ設計の方法もあわせて説明します。

以下のカラムはドリルダウンのためのカラムです。

• volume
• book_publisher
• child_category
• series

これらの情報で親子関係を表現します。親の親がある場合でもGroongaでは各レコードは直接の親だけを格納していれば十分です。各レコードに親の情報だけでなく、親の親の情報も格納する必要はありません。これは正規化した状態のままでよいということです。正規化した状態のままで扱えるため情報の管理が楽です。たとえば、「雑誌」の名前を変更する時は雑誌テーブルの該当レコードを変更するだけでよく、「雑誌」情報を持っているすべてのレコードを変更する必要はないということです。

ドリルダウン用のスキーマ設計は後述します。

以上が設計の概要です。ポイントは次の通りです。

• 横断検索対象の情報はすべて1つのテーブルにまとめる
• 対象の種類を区別する必要がある場合はカラムにその情報を入れて区別する
• 検索条件に使いたい情報を増やす場合はテーブルにカラムを追加する
• 特定のレコードにしかない情報（「論文」にしかない情報や「書籍」にしかない情報）でもカラムを追加してよい
  • 情報が存在しないレコードでは単にカラムに値を設定しない
• ドリルダウン用の情報は正規化したままでよい

検索項目の追加

著者情報を例に検索項目を追加する方法を示します。

著者は複数存在するので次のようにCOLUMN_VECTORで定義します。

column_create Literature authors COLUMN_VECTOR Authors

型はAuthorsテーブルにしていますがShortTextにしてもよいです。テーブルを使っている理由はtypeカラムのときと同じで検索効率および空間効率がよいからです。著者でドリルダウンするなら（今回は説明しません）テーブルにするべきです。計算効率が全然違います。

今回の設計では著者名を主キーにします。

table_create Authors TABLE_HASH_KEY ShortText

同姓同名の著者を別人として扱いたい場合は著者IDを振ってnameカラムを追加します。今回の説明ではそこは本質ではないので単に著者名を主キーにしています。

著者名で完全一致検索する場合は次のようにすれば効率よく検索できます。

select \
  --table Literature \
  --query 'authors:@山田太郎'

著者名で全文検索する場合は追加のインデックスが必要です。

まず、Authors._keyで全文検索するためのインデックスが必要です。

table_create Terms TABLE_PAT_KEY ShortText \
  --default_tokenizer TokenNgram \
  --normalizer NormalizerNFKC100

column_create Terms authors_key \
  COLUMN_INDEX|WITH_POSITION Authors _key

Termsテーブルは他の全文検索用インデックスでも共有可能です。共有するとトークン（全文検索用にテキストを分割したもの）の情報を共有でき、DB全体の空間効率がよくなります。

TermsテーブルではTokenNgramとNormalizerNFKC100を使っています。他にも指定できるものはありますが、これらがバランスがよいので、まずはこれから始めるのがよいです。必要なら後で調整するとよいです。

Terms.authors_keyは全文検索用のインデックスなのでWITH_POSITIONを指定しています。

これで、著者名で全文検索して該当著者を検索できるようになります。しかし、その著者から該当「論文」を見つけることはまだできません。追加で次のインデックスが必要です。

column_create Authors literature_authors \
  COLUMN_INDEX Literature authors

このインデックスはどの著者がどの「論文」の著者かを高速に検索するためのインデックスです。このインデックスも作ることで「著者名で全文検索して著者を見つけ、さらに、その著者がどの論文の著者かを検索する」を実現できます。

検索クエリーは次のようになります。完全一致検索のときとの違いはauthors:@に._keyが加わってauthors._key:@となっているところです。

select \
  --table Literature \
  --query 'authors._key:@山田'

各インデックスカラムの役割を図示すると次の通りです。

authorsは複数の著者が存在するためCOLUMN_VECTORを使っています。また、重複した情報が多くなるため型にテーブルを利用しました。そのため、少し複雑になっています。

titleのように単純な情報の場合は次のようにするだけで十分です。

column_create Literature title COLUMN_SCALAR ShortText
column_create Terms literature_title \
  COLUMN_INDEX|WITH_POSITION Literature title

titleとauthorsを両方検索対象にするには次のようにします。

select \
  --table Literature \
  --match_columns 'title || authors._key' \
  --query 'キーワード'

「論文」（typeが"paper"）だけを検索する場合は次のように--filterで条件を追加します。selectでは--queryと--filterで条件を指定できますが、--queryはユーザーからの入力をそのまま入れる用のオプションで--filterはシステムでより詳細な条件を指定する用のオプションです。

select \
  --table Literature \
  --match_columns 'title || authors._key' \
  --query 'キーワード' \
  --filter 'type == "paper"'

参考：select

1段のドリルダウンの実現

検索対象のデータには2段以上の親子関係のドリルダウンがありますが、まずは1段の親子関係のドリルダウンの実現方法について説明します。

例として次の親子関係のドリルダウンの実現方法について説明します。

• 号
  • 論文

効率的なドリルダウンを実現するためにテーブルを型にしたカラムを作成します。（enum型っぽい使い方とは別の型にテーブルを使う使い方。）

今回の設計では「号」用にVolumesテーブルを作成します。

table_create Volumes TABLE_HASH_KEY ShortText

「論文」はLiteratureテーブルなので、Literatureテーブルにvolumeカラムを作成します。型はVolumesテーブルです。

column_create Literature volume COLUMN_SCALAR Volumes

これでvolumeカラムで効率的にドリルダウンできます。次のようにすれば、「号」でドリルダウンし、その「号」には何件の「論文」があるかを検索できます。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs'

図示すると次の通りです。

次の親子関係も同様に実現できます。

• 出版社
  • 書籍
• シリーズ
  • 書籍（シリーズに属さない書籍もある）

2段以上のドリルダウンの実現

続いて2段以上の親子関係のドリルダウンの実現方法について説明します。

まずは、次の2段のケースについて説明します。

• 雑誌
  • 号
    • 論文

その後、次の3段のケースについて説明します。

• 出版元
  • 雑誌
    • 号
      • 論文

2段の場合もテーブルを型にしたカラムを作成するのは同じです。

今回の設計では「雑誌」用にMagazinesテーブルを作成します。

table_create Magazines TABLE_HASH_KEY ShortText

「号」が所属する「雑誌」を格納するカラムをVolumesテーブルに追加します。

column_create Volumes magazine COLUMN_SCALAR Magazines

これで「号」から「雑誌」をたどることができます。

「号」と「雑誌」でドリルダウンするには次のようにします。ポイントは、.tableでvolumesを指定しているところと、calc_target・calc_typesです。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs' \
  --drilldowns[magazines].table 'volumes' \
  --drilldowns[magazines].keys 'magazine' \
  --drilldowns[magazines].calc_target '_nsubrecs' \
  --drilldowns[magazines].calc_types 'SUM' \
  --drilldowns[magazines].output_columns '_key,_sum'

--drilldowns[${LABEL}]は高度なドリルダウンのためのパラメーターです。

参考：高度なドリルダウン関連のパラメーター

このselectでは以下の2つのドリルダウンを実行します。

• --drilldowns[volumes]: 「号」でドリルダウン
• --drilldowns[magazines]: 「雑誌」でドリルダウン

--drilldowns[magazines].tableで他のドリルダウンの結果を指定できます。指定するとドリルダウン結果をさらにドリルダウンできます。今回のように親子関係がある場合は子のドリルダウン結果から親のドリルダウン結果を計算します。

ただ、普通にドリルダウンすると、カウントした件数は「論文」の件数ではなく、「号」の件数になります。孫（「論文」）でドリルダウンしているのではなく、子（「号」）でドリルダウンしているからです。孫（「論文」）の件数をカウントするには子（「号」）でカウントした件数をさらにカウントする。その設定が次のパラメーターです。

• --drilldowns[magazines].calc_target '_nsubrecs'
• --drilldowns[magazines].calc_types 'SUM'

_nsubrecsには子（「号」）でカウントした孫（「論文」）の件数が入っています。それのSUM（総計）を計算するので孫の件数になります。出力する時は_nsubrecsではなく_sumで参照します。

--drilldowns[magazines].output_columns '_key,_sum'

図示すると次の通りです。

3段になった次のケースも同様です。

• 出版元
  • 雑誌
    • 号
      • 論文

まず、出版元を効率よくドリルダウンするためにPaperPublishersテーブルを作ります。

table_create PaperPublishers TABLE_HASH_KEY ShortText

Magazinesテーブル（「雑誌」）に出版元を格納するカラムを追加します。

column_create Magazines publisher COLUMN_SCALAR PaperPublishers

これで「雑誌」から「出版元」をたどることができます。

「号」と「雑誌」と「出版元」でドリルダウンするには次のようにします。ポイントは、「出版元」のドリルダウンのcalc_targetで_nsubrecsではなく_sumを使っているところです。「出版元」のドリルダウンで「論文」の件数をカウントするには「雑誌」のドリルダウンでカウント済みの「論文」の件数の総計を計算します。そのカウント済みの「論文」の件数が_nsubrecsではなく_sumにあるので_sumを使います。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs' \
  --drilldowns[magazines].table 'volumes' \
  --drilldowns[magazines].keys 'magazine' \
  --drilldowns[magazines].calc_target '_nsubrecs' \
  --drilldowns[magazines].calc_types 'SUM' \
  --drilldowns[magazines].output_columns '_key,_sum' \
  --drilldowns[paper_publishers].table 'magazines' \
  --drilldowns[paper_publishers].keys 'publisher' \
  --drilldowns[paper_publishers].calc_target '_sum' \
  --drilldowns[paper_publishers].calc_types 'SUM' \
  --drilldowns[paper_publishers].output_columns '_key,_sum'

図示すると次の通りです。

次のケースも同様に実現できる。

• 親カテゴリ
  • 子カテゴリ
    • 書籍

子の一覧

親子階層の情報を使って子のレコードを検索する方法を説明します。

ここでは、対象の「出版元」内の「雑誌」の一覧を返すケースを例にして説明します。

まず、対象の「出版元」を絞り込む必要があります。ここでは「出版元」の名前（主キーに入っています）を全文検索して絞り込むとします。

全文検索用のインデックスのテーブルはAuthors._key用に作ったTermsテーブルを流用します。

column_create Terms paper_publishers_key \
  COLUMN_INDEX|WITH_POSITION PaperPublishers _key

これで「出版元」の名前で全文検索できます。しかし、authorsのときと同じで、「出版元」は絞り込めますが、絞り込んだ「出版元」を元に「雑誌」を絞り込むことはできません。「雑誌」も絞り込めるようにするには追加で次のインデックスが必要です。

column_create PaperPublishers magazines_publisher \
  COLUMN_INDEX Magazines publisher

このインデックスは「出版元」をキーにどの「雑誌」がその「出版元」を参照しているかを高速に検索するためのインデックスです。このインデックスがあることで、絞り込んだ「出版元」を元に「雑誌」を絞り込めます。

次のようなクエリーで「出版元」の名前で全文検索し、絞り込んだ「出版元」が発行している「雑誌」を出力できます。

select \
  --table Magazines \
  --match_columns 'publisher._key' \
  --query 'おもしろ雑誌' \
  --output_columns '_key, publisher._key'

他の親子関係のケースも同様に実現できます。

まとめ

Groongaで以下の機能を効率的に実現するためのスキーマ設計方法について説明しました。

• 「論文」と「書籍」を横断全文検索
• 複数カラムで横断全文検索
  • たとえば「タイトル」と「著者」で横断全文検索
• 「論文」だけを全文検索
• 「書籍」だけを全文検索
• 検索結果を任意の親でドリルダウン
  • たとえば「出版元」でドリルダウン
• 指定した親に属する子レコードを検索
  • たとえば「出版元」が発行している「雑誌」を検索

今回の設計を実装したGroongaコマンドはgroonga/groonga-schema-design-exampleにあります。実際に試してみると理解が深まるはずなのでぜひ試してみてください。

クリアコードではGroongaのスキーマ設計もサポートしています。Groongaをもっと活用したい方はお問い合わせください。

ツイートする

フォローする

Linuxでキーボード入力の補助手段としてフットスイッチを活用するには

はじめに

以前片手でのキーボード入力を支援するソフトウェアについてというタイトルで、怪我などで手首などを負傷してしまったときに使える入力方法の一つとしてHalf QWERTY（とそれをソフトウェアとして実装したxhk）を紹介しました。
ある程度はxhkを使うことでなんとかなるのですが、それでも打ちにくいキーというのは存在します。例えばキーを複数組み合わせて押さないといけない場合です。
*1

キーボード以外の選択肢としてのフットスイッチ

片手にこだわらずに使えるものをという観点で探したところ、プログラム可能なフットスイッチというものがあるのをみつけました。

• メカニカルスイッチ搭載 USBフットペダルスイッチ 3ペダル グレー RI-FP3MG

ベースになっているのはPCsensorのモデルのようです。

• USB Foot Control Keyboard,Three Switch Pedal

複数のモデルがあり、別のモデルであるRI-FP3BKはLinuxでの実績がすでにあるようでした。

RI-FP3MGそのものの言及はありませんが、フットスイッチそのものに設定が保持されるタイプなので、設定自体はLinuxからできなくてもいいかということで試してみました。

フットスイッチを認識させる

フットスイッチをPCに接続してlsusbの結果を確認すると、次のIDで認識されていました。

% lsusb
（省略）
Bus 002 Device 002: ID 0c45:7404 Microdia

フットスイッチをLinuxから設定するには

標準ではWindowsの設定アプリが付属しているのでそちらを使えばいいのですが、認識されたIDをもとに検索すると、次のリポジトリを見つけました。

• https://github.com/rgerganov/footswitch

対応しているIDのリストに0c45:7404があったので、Linuxでも使えそうです。

footswitchはREADME.mdに記載の次の手順でビルドできました。

% sudo apt install libhidapi-dev
% git clone https://github.com/rgerganov/footswitch.git
% cd footswitch
% make

ビルドが完了すると、footswitchとscytheの2つのバイナリができます。0c45:7404に対応しているのはfootswitchなのでそちらを使います。

フットスイッチの設定方法

-rオプションを指定するとフットスイッチの現在の設定値を確認できます。

% sudo ./footwswitch -r
[switch 1]: a
[switch 2]: b
[switch 3]: c

出荷直後は、a、b、cがそれぞれのスイッチに割りあてられていました。

スイッチ自体は3つありますが、次の2つの用途に使ってみることにしました。

• 日本語入力のON/OFFをShift+Spaceにしているので、スイッチ1に割りあてる
• tmuxのプレフィクスをCtrl+Tにしているので、スイッチ3に割りあてる

上記の2つの設定を行うには、次のコマンドを実行します。

% sudo ./footswitch -1 -m shift -k space -3 -m ctrl -k t

-1 -m shift -k spaceの部分が「スイッチ1が押されたら、モディファイアキーとしてShiftキーを、通常のキーとしてスペースを押した状態にする」ための指定です。

-3 -m ctrl -k tの部分が「スイッチ3が押されたら、モディファイアキーとしてCtrlキーを、通常のキーとしてtを押した状態にする」ための指定です。

なお、上記のようにスイッチ2の設定を一緒に指定しない場合には、スイッチ2の設定がクリアされるので注意が必要です。（特定のスイッチのみ指定して設定を上書きみたいなことはできない）

フットスイッチの設定がうまくいかない場合

footswitchはキー入力だけでなく、マウスカーソルの移動もエミュレートできるようです。（そちらは試していない）
README.mdを参照する限り、かなり細かな設定ができそうに思いますが、試した限りでは次の場合には期待通りには動作しません。

• CtrlとCapsLockキーを入れ換えている場合

CtrlとCapsLockキーを入れ換えている場合には、-m ctrl -k tが機能せず、tだけ打鍵したかのように振る舞います。

• How to use footswitch with ctrl:swapcaps?

この問題は解決していませんが、キー割り当てをCtrlにこだわらなければ回避策があります。単純なやりかたですが、Ctrlの代わりに別のキーとの組み合わせにするなどです。

幸い、Ctrl+Tを使いたかったのはtmuxのプレフィクスとしてだったので、次のようにしてAlt+Tをfootswitchで指定することにしました。（ターミナルで作業する範囲においては、他のキー割り当てと衝突しにくい）

% sudo ./footswitch -1 -m shift -k space -3 -m alt -k t

まとめ

今回は、キーボード入力の補助手段としてのフットスイッチを紹介しました。
もし、xhkなどを駆使していても追いつかない状況になったら、選択肢の一つとして試してみるのもよいかもしれません。

ツイートする

フォローする

JavaScriptのArrayでuniqする8つの方法（と、その中で最速の方法）

この記事はQiitaとのクロスポストです。

みなさんはuniqというコマンドやメソッドをご存じでしょうか？

LinuxやmacOSのシェルのコマンドとして使えるuniqは、与えられた入力の中で（連続する）同じ値を重複と見なして除外するというコマンドです。例えばこんな風に使います。

$ cat /var/log/apache2/access.log | cut -d ' ' -f 1
192.168.0.12
192.168.0.10
192.168.0.12
192.168.0.12
192.168.0.11
192.168.0.10
192.168.0.11
192.168.0.11
$ cat /var/log/apache2/access.log | cut -d ' ' -f 1 | sort | uniq
192.168.0.10
192.168.0.11
192.168.0.12

プログラミング言語でも似たような機能を持っている物があります。例えばRubyでは、Arrayクラスのuniqメソッドを使うと配列の要素から重複を簡単に取り除くことができます。

[0,3,2,1,4,2,3,1,1,2,3,5,2,3,1,2,3,1,1,3,3,1,2].uniq
# => [0, 3, 2, 1, 4, 5]

ここで標題のJavaScriptの話をすると、JavaScript自体の言語仕様はES6やES2015、ES2017などを経て強化されてきているのですが、残念ながら上記のようなことを一発でやる機能は仕様化されていません。やりたければ、既存の機能を組み合わせて実現するほかありません。

uniqのやり方色々

やり方を紹介した記事は、配列の重複をはじく、もしくは重複を取り出す - Qiitaなど既にいくつも例がありますが、ここでは改めてなるべく多くのパターンを挙げてみる事にします。

Objectのキーを使う方法

古典的なやり方としては、Objectのプロパティ名を使う方法があります。JavaScriptではObjectのインスタンスは一種のハッシュ（連想配列）として機能し、プロパティ名（＝ハッシュのキー）に重複はあり得ないため、配列の要素が登場済みかどうかの判定をするのに使うことができます。

function uniq(array) {
  const knownElements = {};
  const uniquedArray = [];
  for (let i = 0, maxi = array.length; i < maxi; i++) {
    if (array[i] in knownElements)
      continue;
    uniquedArray.push(array[i]);
    knownElements[array[i]] = true;
  }
  return uniquedArray;
};

const array = [0,3,2,1,4,2,3,1,1,2,3,5,2,3,1,2,3,1,1,3,3,1,2];
console.log(uniq(array));
// => [0, 3, 2, 1, 4, 5]

for文の箇所を今風の書き方に改めると、以下のようになるでしょうか。

function uniq(array) {
  const knownElements = {};
  const uniquedArray = [];
  for (const elem of array) {
    if (elem in knownElements)
      continue;
    uniquedArray.push(elem);
    knownElements[elem] = true;
  }
  return uniquedArray;
}

ただ、この方法には一つ致命的な欠陥があります。それは、Objectのプロパティ名は必ず文字列として扱われるため、文字列化できない要素や、文字列化した時に区別がつかない要素を含む配列に対しては使えないという点です。JavaScriptではDOMのノードや何らかのクラスのインスタンスなどのオブジェクトを格納した配列を使うことが多いので、これでは使える場面が非常に限定されてしまいます。

Arrayの便利メソッドを使う

ArrayのインスタンスのindexOfメソッドを使うと、任意の形式のオブジェクトについて、配列に含まれているかどうかを容易に識別することができます。これを使うと、先の例は以下のように書き直せます。

function uniq(array) {
  const uniquedArray = [];
  for (const elem of array) {
    if (uniquedArray.indexOf(elem) < 0)
      uniquedArray.push(elem);
  }
  return uniquedArray;
}

ES2016で追加されたArrayのincludesメソッドは、渡されたオブジェクトが配列に含まれているかどうかを真偽値で返すという物です。これを使うと、indexOfの戻り値の特性（配列に含まれていなければ-1を返す）を知らない人でも読みやすいコードになります。

function uniq(array) {
  const uniquedArray = [];
  for (const elem of array) {
    if (uniquedArray.includes(elem))
      uniquedArray.push(elem);
  }
  return uniquedArray;
}

ES5.1で追加されたArrayのfilterメソッドは、条件に当てはまる要素だけを含んだ配列を生成するという物です。これを組み合わせると、forループを書かずに同様のことができます。

function uniq(array) {
  return array.filter(function(elem, index, self) {
    return self.indexOf(elem) === index;
  });
}

元の配列の中で2回目以降に登場した（同じ要素が既に登場済みの）要素は、indexOfの結果＝先頭からその要素を探した時の位置が、index＝要素自身の位置と一致しません。そういった要素を除外すれば、各要素が1回ずつしか出現しない配列を取り出せる、という訳です。一時的な配列を作らないで済ませるために、2つ前の例とは異なるindexOfの使い方をしています（先の例では一時的な配列に対するindexOfなのに対し、こちらは元の配列に対するindexOfです）。

アロー関数を使うと、もう少しすっきり書けます。

function uniq(array) {
  return array.filter((elem, index, self) => self.indexOf(elem) === index);
}

Mapを使う

ES2015で追加されたMapは、それまでのObjectを使った擬似的な連想配列（ハッシュ）とは異なり、任意のオブジェクトをキーとして使うことができる本物の連想配列です。これを使うと、先のObjectを使った例をより完全な物にすることができます。

function uniq(array) {
  const knownElements = new Map();
  const uniquedArray = [];
  for (const elem of array) {
    if (knownElements.has(elem))
      continue;
    uniquedArray.push(elem);
    knownElements.set(elem, true);
  }
  return uniquedArray;
}

この例では配列を先に用意していますが、実はその必要はありません。というのも、Mapはkeysメソッドを使うとキーだけの集合を得ることができるからです。keysメソッドの戻り値はイテレータなので、ES2015で追加されたArray.fromを使って配列に変換することができます。

function uniq(array) {
  const knownElements = new Map();
  for (const elem of array) {
    knownElements.set(elem, true); // 同じキーに何度も値を設定しても問題ない
  }
  return Array.from(knownElements.keys());
}

Setを使う

Mapに比べるとややマイナーですが、ES2015で追加されたSetという機能もあります。Mapがキーと値のペアを取り扱うのに対して、SetはMapでいう所のキーだけ、つまり、一意な値を格納する集合です。要素の重複があり得ないArrayのような物、とも言えます。これを使うと、先の例はこう書き直せます。

function uniq(array) {
  const knownElements = new Set();
  for (const elem of array) {
    knownElements.add(elem); // 同じ値を何度追加しても問題ない
  }
  return Array.from(knownElements);
}

しかし、これはもっと簡潔に書き直すことができます。Setはコンストラクタの引数としてイテレータや配列を受け付けるため、new Set(array)とすれば、渡した配列の要素の中から一意な値だけの集合を得ることができます。それをArray.fromで配列に戻せば、即ち「配列から重複を取り除く」のと同じ事になります。

function uniq(array) {
  return Array.from(new Set(array));
}

2019年1月5日追記：Array.fromではなくES2015のスプレッド構文を使うと、以下のようにも書けます。

function uniq(array) {
  return [...new Set(array)];
}

どの方法が一番おすすめ？

ということで、JavaScriptで配列をuniqする方法を色々と列挙してみましたが、どの方法が一番おすすめと言えるでしょうか。

判断の優先順位

その答えを考える前に、何を以て「良い」と判断するかをまずは明らかにする必要があります。具体的には、以下の各観点に優先順位を付けなくてはなりません。

• コードの量が短い事
• 古い実行環境でも使える事
• 処理対象の配列が巨大でも高速である事
• 処理対象の配列が多数でも高速である事

というのも、上記の例のそれぞれには一長一短あり、すべての条件を同時に満たす事は困難だからです。

コードの量については、見ての通りです。コードゴルフなどの文脈や、1バイトでもソースの量を減らさなくてはならないようなシビアな状況であれば、多少動作速度が遅くても文字数の短いコードにする必要があるでしょう。そうでない限りは、記述量が多くなっても速度の速いコードを採用する方が良いでしょう。

実行環境（ブラウザやNodeのバージョン）については、想定する環境でサポートされていない機能を使用している方法は、当然ながら採用できません。MapやSetを使う方法は、トランスパイラを使う事で古い環境でも動作させる事はできますが、その場合、変換後のコードがどのパターンになるかによって動作速度が変わってきます。

動作速度については、処理対象の配列の要素数と実行回数によって最適な方法が変わってきます。

まず重要な観点として、計算量の問題があります。アルゴリズムごとに計算量には差があり、配列の要素数や実行回数が多い場面では、なるべく計算量の小さいアルゴリズムの方が望ましいです。

また別の観点として、オーバーヘッドの問題があります。JavaScriptでは関数の呼び出しやオブジェクトの作成、値の型の変換など、純粋な計算量とは別の部分で処理に時間がかかる部分があります。実行回数が少なければオーバーヘッドはほとんど無視できますが、多いとほとんどの処理時間がオーバーヘッドによる物という事になる場合もあります。

各アルゴリズムの処理速度の比較

それぞれのアルゴリズムで同じ配列を条件を変えながら処理するベンチマークをFirefox 64上で実行した場合の結果で、それぞれの優劣を見ていきましょう。まずは、要素数10の配列を10万回から50万回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）で、グラフの線が上にあるほど処理が遅く、下にあるほど処理が速い事を示しています。

このように要素数の少ない（サイズの小さい）配列を処理する場面では、forループやArrayのメソッドだけを使う方法がおすすめという事がグラフから見て取れます。MapやSetを使う方法は、このくらいの要素数だとオーバーヘッドが非常に大きいようです。

次は、要素数300の配列を2500回から12500回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

今度は結果が逆転しました。最速なのはSetを使う方法で、最も遅いのはArrayのfilterを使う方法という結果になっています。これは、Arrayのfilterを使うアルゴリズムが本質的に二重ループである（いわゆる、計算量がO(n^2)のアルゴリズム）ことが原因です。この結果からは、要素数が増えてくるとオーバーヘッドよりも計算量の方が支配的になってくるという事が分かります。

次は、要素数10000の配列を100回から500回まで処理した結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

もはやオーバーヘッドは完全に無視できるレベルになり、計算量が少ない物が明白に高速という結果になりました。ArrayのindexOfやincludesを使う方法とfilterを使う方法で、本質的なアルゴリズムそのものは大差ない（どちらも二重ループ）のに、forループとfilterとでパフォーマンスに大きな差が現れているのは何故でしょうか？ その答えは後ほど説明しましょう。

今度は指標を変えて、要素数がどの程度になったあたりから計算量とオーバーヘッドの問題が逆転するかを見てみます。以下は、要素数を100から1000まで増やしながら5000回処理した場合の結果です。グラフの縦軸は処理に要した時間（ミリ秒）です。

実行環境の性能による部分が大きいと考えられますが、今回の実験環境においては要素数が300を超えたあたりで計算量の増大がオーバーヘッドを追い抜くという結果になりました。しかしやはりアルゴリズム的に差が無い筈のuniqByIndexOfやuniqByIncludesとuniqByFilterやuniqByFilterArrowの間で大きな差がある……というか、filterを使うと指数関数的に処理時間が増大するのにforループでは線形の増加に留まっているように見えます。

この謎を解くために、次はNightly 66.0a1での結果を見てみましょう。JavaScriptエンジンの最適化が進んでいるためか、同じパラメータだと数字が小さくなりすぎてしまったため、今度はパラメータを「要素数を100から200刻みで1900まで増やしながら10000回処理」に変えています。

グラフの傾向を見ると、計算量が大きいアルゴリズムであるindexOfやincludesを使った物はいずれも指数関数的な増大を見せています。1つ前の結果でuniqByIndexOfやuniqByIncludesが線形の増加に見えたのは、

• Firefox 64時点ではforループは最適化されていたが、filterのループは最適化されていなかった。
• 最適化の結果、forループを使った物の結果の指数関数的な増大が顕著になり始めるタイミングが右にずれていた（グラフが横に引き延ばされていた）。そのため、グラフの描画範囲では線形の増加に見えていた。
• Nightly 66ではfilterも最適化されたため、アルゴリズムが本質的に似ている4つの項目のグラフが再び接近するようになった。

という事だったようです。

また、それでもまだfilterを使った方法の方が遅いのは、indexOfやincludesを使った方法では検索対象の配列がuniq後の配列（＝小さい配列）なのに対し、filterを使う方法ではuniq前の配列（＝大きい配列）を対象にしているせいで、その分余計な時間がかかったからだと考えられます。

2019年1月5日追記：new Set()とスプレッド構文の組み合わせを加えて再計測した結果も掲載しておきます。

検証環境上では、スプレッド構文を使うとArray.fromより若干速いという結果が得られました。

まとめ

以上、JavaScriptでArrayのuniqを実現する様々な手法をご紹介しました。

Webのフロントエンドの開発では計算量が問題になるような事はそう多くないのではないかと思われますが、Nodeで大量のリクエストを捌くような場面や、どれだけの量のデータが渡されるか事前に予想できないライブラリ開発のような場面では、なるべく計算量が小さいアルゴリズムを採用する事が望ましいです。

また、1つの事を実現するのに複数のやり方がある場合には、何を優先するかを事前にきちんと明らかにし、数値で比較可能な場合は特に、この例のようにベンチマークを取ってそれぞれのやり方の優劣を比較する事が大事です。

性能測定の結果を踏まえると、処理速度的には、少なくとも今回の実験環境においては

• SetとArray.fromまたはスプレッド構文の組み合わせが最もおすすめ。
• ただし、「要素数が小さい配列を」「頻繁に（多数）処理する」という前提がある場合には、SetやMapを使わない方法の方がおすすめ。

という事が言えそうです。ベンチマークに使用したスクリプトはGistで公開していますので、皆さんもぜひお手元で試してみて下さい。

ツイートする

フォローする

Ruby 2.6.0とtest-unitとデータ駆動テスト

Rubyのbundled gemのtest-unitをメンテナンスしている須藤です。

歴史

test-unitはxUnitスタイルのテスティングフレームワークです。Rubyのテスティングフレームワークの歴史（2014年版）にまとめてある通り、Ruby本体に標準添付されています。

Rubyに標準添付されているライブラリーには実は次の3種類あります。

• ただの標準添付ライブラリー（例：URI）
  • requireするだけで使えるライブラリー
• default gem（例：csv）
  • requireするだけで使えるライブラリー
  • RubyGemsで更新できる
  • Gemfileでgemを指定しなくても使える
• bundled gem（例：test-unit）
  • requireするだけで使えるライブラリー
  • RubyGemsで更新できる

どれも標準添付ライブラリーなのでrequireするだけで使えます。違いはRubyGems・Bundlerとの関係です。

ただの標準添付ライブラリーはRubyGemsでアップグレードすることはできませんし、Bundlerで特定のバージョンを指定することもできません。使っているRubyに含まれているものを使うだけです。

default gemはRubyGemsでアップグレードすることもできますし、Bundlerで特定のバージョンを指定することもできます。Bundlerを使っていてgem名を指定しなかった場合は使っているRubyに含まれているものを使います。

bundled gemはRubyGemsでアップグレードすることもできますし、Bundlerで特定のバージョンを指定することもできます。Bundlerを使っていてgem名を指定しなかった場合は使えません。Bundlerを使っていなければrequireするだけで使えます。

Ruby 2.6.0でより高速になったcsvはRuby 2.6.0からdefault gemになっています。

test-unitはRuby 2.2.0で再度標準添付されるようになってからbundled gemになっています。

そんなtest-unitのデータ駆動テスト機能をさらに便利にしたものがRuby 2.6.0に入っています。

データ駆動テスト

データ駆動テストとは同じテスト内容をいろいろなデータで実行するテスト方法です。パラメーター化テストと呼ばれることもあります。いろいろな入力に対するテストを簡潔に書きたいときに便利です。

test-unitでは結構前からデータ駆動テストをサポートしています。

たとえば、正の数同士の足し算と負の数同士の足し算をテストすることを考えます。データ駆動テスト機能を使わない場合は次のようにそれぞれのケースについてテストを作ります。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  def test_positive_positive
    assert_equal(3, my_add(1, 2))
  end

  def test_negative_negative
    assert_equal(-3, my_add(-1, -2))
  end
end

データ駆動テスト機能を使う場合はテストは1つで、テストに使うデータを複数書きます。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  data("positive + positive", [3, 1, 2])
  data("negative + negative", [-3, -1, -2])
  def test_add(data)
    expected, augend, addend = data
    assert_equal(expected, my_add(augend, addend))
  end
end

データが増えてくるほど、データ駆動テスト機能を使った方がテストを書きやすくなります。データを追加するだけで済むからです。ただ、読みやすさは従来のテストの方が上です。テストに使うデータがベタ書きされているからです。

test-unitのデータ駆動テスト機能をもっと知りたくなった人はRuby用単体テストフレームワークtest-unitでのデータ駆動テストの紹介を参照してください。

データ表生成機能

Ruby 2.6.0に入っているtest-unitではデータ駆動テストがさらに便利になっています。

まだなんと呼ぶのがよいか決めかねているのですが、今のところデータ表（data matrix）と呼んでいるものを生成する機能が入っています。

データ表というのは各テストで使うデータをまとめたものです。前述のテストの場合は次のようになります。dataを使う毎に1行増えます。

このデータ表をいい感じに生成する機能が入っています。

前述のテストで正の数と負の数を足す場合もテストしたくなったとします。その場合、従来のデータ駆動テスト機能の書き方では次のように書きます。dataを2つ増やしています。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  data("positive + positive", [3, 1, 2])
  data("negative + negative", [-3, -1, -2])
  data("positive + negative", [-1, 1, -2]) # 追加
  data("negative + positive", [1, -1, 2])  # 追加
  def test_add(data)
    expected, augend, addend = data
    assert_equal(expected, my_add(augend, addend))
  end
end

データ表は次のようになります。

データ表生成機能を使うと次のように書けます。dataの第一引数にSymbolを指定しているところがポイントです。テストに渡されるデータはHashになっていてキーがシンボルで値が対象データです。

require "test-unit"

class TestAddDataMatrix < Test::Unit::TestCase
  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

これで次のデータ表を生成できます。

期待する結果（expected）は生成できないのでRuby組み込みのInteger#+の結果を使っています。これは実は大事なポイントです。データ表生成機能を使えるのは次の場合だけです。

• 期待する結果がデータに依らず一意に定まる
• データから期待する結果を計算できる

今回の場合は期待する結果を計算できるので使えました。

なお、期待する結果は必ずしも正しい結果を返すはずの既存の実装（今回の場合はInteger#+）を使わなくても大丈夫です。次のように「エンコードしてデコードしたら元に戻る」ようなときでもデータ表生成機能を使えます。これは性質をテストしているケースです。（性質をテストすることについてはここを参照してください、とか書いておきたいけど、どこがいいかしら。）

assert_equal(raw_data,
             decode(encode(raw_data)))

この例ではパラメーターはaugendとaddendの2つでそれぞれに正と負があるので、4パターンでしたが、パラメーター数が増えたりバリエーションが増えると一気にパターンが増えます。そのときはこのデータ表生成機能が便利です。

なお、この機能はRed Chainer（Rubyだけで実装しているディープラーニングフレームワーク）で使うために作りました。もともとRed Chainerのテスト内でデータ表を生成していたのですがこの機能を使うことでだいぶスッキリしました。

データを使い回す

実はRed Chainerのテストをスッキリさせるためにはデータ表を生成するだけでは機能が足りませんでした。同じデータ表を複数のテストで共有する機能が必要でした。

前述の例で言うと、同じデータ表を足し算のテストでも引き算のテストでも使いたいという感じです。コードで言うと、以下をもっといい感じに書きたいということです。

require "test-unit"

class TestCalc < Test::Unit::TestCase
  data(:number1, [1, -1])
  data(:number2, [2, -2])
  def test_add(data)
    number1 = data[:number1]
    number2 = data[:number2]
    assert_equal(number1 + number2,
                 my_add(number1, number2))
  end

  data(:number1, [1, -1])
  data(:number2, [2, -2])
  def test_subtract(data)
    number1 = data[:number1]
    number2 = data[:number2]
    assert_equal(number1 - number2,
                 my_subtract(number1, number2))
  end
end

そこで、dataメソッドにkeep: trueオプションを追加しました。これで一度dataを書けば後続するテストでも同じデータを使うようになります。

require "test-unit"

class TestCalc < Test::Unit::TestCase
  data(:number1, [1, -1], keep: true) # keep: trueを追加
  data(:number2, [2, -2], keep: true) # keep: trueを追加
  def test_add(data)
    number1 = data[:number1]
    number2 = data[:number2]
    assert_equal(number1 + number2,
                 my_add(number1, number2))
  end

  # ここにdataはいらない
  def test_subtract(data)
    number1 = data[:number1]
    number2 = data[:number2]
    assert_equal(number1 - number2,
                 my_subtract(number1, number2))
  end
end

データ表を複数生成する

実はRed Chainerのテストをスッキリさせるためにはデータを使い回せても機能が足りませんでした。1つのテストに対して複数のデータ表を生成する機能が必要でした。

前述の例で言うと、小さい数同士と大きい数同士で別のデータ表を作りたい、ただし、小さい数と大きい数の組み合わせはいらないという感じです。（わかりにくい。）

データ表で言うと次の2つのデータ表を使う感じです。

小さい数用のデータ表：

大きい数用のデータ表：

コードで言うと、以下をもっといい感じに書きたいということです。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add_small(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end

  data(:augend, [10000, -10000])
  data(:addend, [20000, -20000])
  def test_add_large(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

そこで、dataメソッドにgroup:オプションを追加しました。同じグループ毎にデータ表を生成します。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  data(:augend, [1, -1], group: :small) # 小さい数用
  data(:addend, [2, -2], group: :small) # 小さい数用
  data(:augend, [10000, -10000], group: :large) # 大きい数用
  data(:addend, [20000, -20000], group: :large) # 大きい数用
  def test_add(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

setupでもデータを参照可能にする

実はRed Chainerのテストをスッキリさせるためにはデータ表を複数作れても機能が足りませんでした。テスト実行中にデータを参照しやすくする機能が必要でした。

従来のデータ駆動テスト機能ではテストメソッドの引数でデータを渡していました。そのため、setup中でデータを参照できませんでした。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  def setup
    # ここでデータを参照できない
  end

  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

Red Chainerのテストではデータを前処理したかったので次のように明示的に前処理メソッドを呼んでいました。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  def my_setup(data)
    # 前処理
  end

  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add(data)
    my_setup(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

これは微妙なのでdataでデータを参照できるようにしました。

require "test-unit"

class TestAdd < Test::Unit::TestCase
  def setup
    p data # データを参照できる！
  end

  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add(data)
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

また、テストでも引数でデータを受け取らなくてもよくなりました。（従来どおり受け取ってもよいです。）

require "test-unit"

class TestAdd < Test::Unit::TestCase
  def setup
    p data # データを参照できる！
  end

  data(:augend, [1, -1])
  data(:addend, [2, -2])
  def test_add # test_add(data)としなくてもよい！
    augend = data[:augend]
    addend = data[:addend]
    assert_equal(augend + addend,
                 my_add(augend, addend))
  end
end

まとめ

Red Chainerのためにtest-unitにデータ表生成機能を追加しました。Ruby 2.6.0にもこの機能を使えるtest-unitが入っています。ぜひ活用してください。

なお、Ruby 2.6.0でなくてもRubyGemsで新しいtest-unit（3.2.9以降）にアップグレードすれば使えます。Red Chainerでもそうやって使っています。

Red Chainerの開発に参加したい人はRed Data Toolsに参加してください。オンラインのチャットか東京で毎月開催している開発の集まり（次回は2018年1月22日）でどうやって進めていくか相談しましょう。

ツイートする

フォローする

Ruby 2.6.0とより高速なcsv

Rubyの標準添付ライブラリーのcsvをメンテナンスしている須藤です。

歴史

csvは名前の通りCSVを読み書きするための便利ライブラリーです。

もともとRuby本体とは別に開発されていたのですが、Ruby 1.8.0のときにRuby本体にバンドルするようになりました。dRubyやREXMLがRuby本体にバンドルされたのも同じタイミングです。Ruby 1.8.0のときにバンドルするライブラリーをすごく増やしたのです。（その頃の様子がわかるURLをここに置いておきたかったけど見つけられなかった。。。）

Rubyではcsvのようにrequireするだけで使えるライブラリーを「標準添付ライブラリー」と呼んでいます。Stringのようにrequireしなくても使えるライブラリーは。。。なんだろう。組み込みクラスかしら。

その後、Ruby 1.9.0のタイミングで実装をFasterCSVに置き換えました。FasterCSVは名前の通りもともとのcsvよりも速いライブラリーです。もともとのcsvもFasterCSVもRubyだけで実装してあり、Cを使っていません。Rubyで実装したCSVライブラリーでは最速です。今のcsv（FasterCSVベースのcsv）よりも速いといっているCSVライブラリーはCを使っているはずです。

そんなcsvをさらに速くしたものがRuby 2.6.0に入っています。

FasterCSV実装がなぜ速いか

FasterCSVがなぜ速いかというと各行をline.split(",")でパースしているからです。String#splitはCで実装されているので速いのです。

ただ、世の中にはline.split(",")でパースできないCSVがたくさんあります。たとえば、次のようなCSVです。

a,"b,c",d

このCSVではダブルクォートで囲んでいる中にコンマがあるのでline.split(",")では次のようにパースしてしまいます。

[
  "a",
  "\"b",
  "c\"",
  "d",
]

このようなケースにも対応するために、FasterCSVはline.split(",")した後の各要素のダブルクォートの数を数えます。ダブルクォートの数が偶数ならダブルクォートの対応が取れていて、奇数なら取れていないというわけです。ダブルクォートの対応が取れていない場合は後続する要素と連結します。

このようにして速さを維持したまま複雑なCSVもパースできるようになっています。ただ、複雑なCSVをパースするときは速度が落ちてしまいます。次の表はcsvが使っているベンチマークを使ったパース性能の計測結果です。複雑になるほど性能が落ちている（単位時間あたりでのパース回数が減っている）ことがわかります。

Ruby 2.6.0に入っているcsvでは次のようになります。「ダブルクォートあり」の場合は少し性能が落ちています（207から194に減っている）が、ダブルクォート内が複雑になっても「ダブルクォートあり」と性能が変わりません。（「コンマあり」と「改行あり」が193と192で194とほとんど変わらない。）「ダブルクォートなし」の場合は少し性能があがっています。（373から401に増えている）

Ruby 2.6.0のcsvがなぜ速いか

「最速」だったcsvがどうやってさらに速くなったかというとStringScannerを使うようになったからです。StringScannerは標準添付ライブラリーの1つで、正規表現を使って高速に文字列をスキャンできます。

ただ、単にStringScannerを使っても「最速」だったcsvよりも速くはなりません。line.split(",")は強敵です。@284kmが取り組んだ、まずline.split(",")をStringScannerに置き換えるpull requestでも全体的に遅くなっています。ただ、これでも高速にするための工夫をした後の結果です。Red Data Toolsの開発の集まりなどで@284kmと一緒に高速にするための書き方を模索していました。その結果、次の知見を得ました。

• どの正規表現を使ってどの順番でスキャンするかが重要

StringScannerを使ったコードは次のようなコードになります。ポイントは「次はこういう値が来るはず、来なかったらエラー」というのをつなげていくところです。

row = []
scanner = StringScanner.new(line)
column_value = scanner.scan(/[^",\r\n]+/) # カラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字（コンマ）
column_value = scanner.scan(/[^",\r\n]+/) # 次のカラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字（コンマ）
raise "extra data" unless scanner.eos?    # すべてのデータを使ったか
p row

CSVのように複雑なものだと、「次はこういう値が来るはず、来なかったら別のこの値なはず」というようにフォールバックしていきます。たとえば、「ダブルクォートで囲まれていない値があるはず、なかったらダブルクォートで囲まれた値のはず」といった具合です。

line.split(",")を超える性能を出すためにはフォールバックをいかに減らすかが大事になります。フォールバックのオーバーヘッドがあるとline.split(",")に負けてしまうのです。

フォールバックを減らすには「次はこういう値が来るはず」ができるだけ当たるような順番にします。カラムの値の次はコンマがきやすいので、次の2つでは後者の方がフォールバックの回数が減ります。

カラムの値もコンマも並列に扱う（フォールバックが多い）：

row = []
column_value = nil
until scanner.eos?
  if scanner.scan(/[^",\r\n]+/) # カラムの値
    column_value = scanner.matched
  elsif scanner.scan(/,/) # コンマ
    row << column_value
    column_value = nil
  else
    raise "invalid"
  end
end
row << column_value if column_value
p row

カラムの値の後はコンマがくるはず（フォールバックが少ない）：

row = []
until scanner.eos?
  if (column_value = scanner.scan(/[^",\r\n]+/)) # カラムの値
    if scanner.scan(/,/) or scanner.eos?
      row << column_value
    else
      raise "no comma"
    end
  else
    raise "invalid"
  end
end
p row

line.split(",")に勝つには正規表現のマッチ回数をいかに減らすかを頑張る必要があります。これが基本的なコンセプトです。それではさらに具体的な方法を説明していきます。

行ごとの処理をやめる

line.split(",")ベースのアプローチでは次のようにダブルクォート中が複雑になる処理で性能劣化が大きかったです。

これを解決するために行に分割してから処理することをやめました。

行に分割せずに、ダブルクォート中がどうなっていても（たとえば改行文字を含んでいても）統一的に処理することで性能劣化を防ぎました。

これが一番大変でした。というのは、パースするロジックをすべてStringScannerらしく書き換える必要があるからです。

書き換えた後は次のようなコードになりました。すっきりですね。

row = []
while true
  value = scanner.scan(/[^",\r\n]+/)
  if scanner.scan(/,/)
    row << value
  elsif scanner.scan(/\r\n/)
    row << value
    p row
    row = []
  elsif scanner.eos?
    row << value
    p row
    return
  else
    raise "invalid"
  end
end

これでダブルクォートを使っていても性能劣化しなくまりました。（ダブルクォート中に改行がある方が速くなっているのはなぜだ。。。）

これを実現することによりコードをメンテナンスしやすくなり、最適化や機能追加をしやすくなりました。line.split(",")ベースのコードも200行未満の実装なのでそんなに長すぎるわけではないのですが、状態が多くて適切な場所に適切な処理を入れるのが難しかったのです。

以前と同じくらいの性能にできればStringScannerベースのパーサーで開発を進められます。

loopをwhile trueにする

性能改善の大きなポイントは正規表現のマッチ回数を減らすことですが、それ以外の部分でも少しずつ性能改善できます。その1つでやりやすいものがloop do ... endではなくwhile true ... endでループするようにすることです。

Rubyを使っている場合はdo ... endを使いたいので私は普段は次のようにループを書きます。

loop do
  # ...
end

しかし、今回のように性能改善したいケースでは次のようにwhile true ... endを使った方が高速です。これはloopだとdo ... endの中でスコープが変わるのでその準備をしないといけないのに対し、whileはスコープが変わらないのでその準備が必要ないからです。

while true
  # ...
end

csvのケースではwhile trueの方が15%ほど高速です。

100msでのパース回数：

string[start...end]をstring[start, end - start]にする

Stringには文字列データの一部を共有する機能があるため、既存のStringの一部で必要なStringを作れる場合は共有機能を使うことで高速になります。

文字列データを共有するにはString#[]を使います。String#[]は便利なメソッドでいろんな引数を受けつけます。たとえば、次の2つは同じ結果を返します。

string[1...6]
string[1, 5]

ただし、string[1, 5]の方が速いです。これは、引数が2つの場合は特別扱いされているためです。

csvの場合、string[1, 5]のスタイルを使った場合の性能改善の度合いは軽微です。

必要になるまで処理を遅らせる

みなさんはCSV#lineというメソッドがあるのを知っていますか？私は知りませんでした。このメソッドは最後に処理した行そのもの（パース前の行）を返します。普通はパース結果だけを使うので、この処理のために通常のパース処理が遅くなるのは微妙です。そのため、このための情報を必要になったときにはじめて取得するように変更しました。

微妙に速くなっています。

通常は必要ない処理を必要になるまで処理しないことによる高速化はCSVの書き込み処理で顕著です。

CSVはCSVを読み書きできるのでインスタンスを作るときに読み書き両方用の初期化をしていました。そのため、CSVを読むだけ、書くだけのときに余計な処理をしていました。

この読む用の初期化・書く用の初期化を必要になるまで遅延するようにしました。これにより、読むだけのときは書く用の初期化を一切しなくなり、高速になります。

以下は書き込み処理のベンチマーク結果です。

100msでの処理回数：

2倍ほど速くなっています。CSV.generate_lineはCSVオブジェクトを作らずに1行生成する便利機能ですが、たくさんの行を生成する時はCSVオブジェクトを作った方が高速です。これは、CSV.generate_lineの場合は1行生成する度に書く用の初期化を毎回しなければいけないためです。

つまり、次のように書くのは遅いということです。

rows.each |row|
  puts CSV.generate_line(row)
end

それよりは次のように書いた方が速いです。

output = ""
csv = CSV.new(output)
rows.each |row|
  csv << row
end
puts output

String#each_charではなくString#indexを使う

読む用の初期化時に改行文字を自動検出しているのですが、そこも高速化できた処理でした。

従来はString#each_charで一文字ずつ確認していたのですが、そこをString#indexを使って書き換えました。次のような感じです。

cr_index = sample.index("\r")
lf_index = sample.index("\n")
if cr_index and lf_index
  if cr_index + 1 == lf_index
    "\r\n"
  elsif cr_index < lf_index
    "\r"
  else
    "\n"
  end
elsif cr_index
  "\r"
elsif lf_index
  "\n"
else
  :auto
end

String#indexを使うとCレベルで文字チェックをできるので速くなりました。（後でどのくらい速くなったか追記できるといいな。）

なんか野暮ったいコードなのでもう少しシュッとできるといいですね。

効果がなかった高速化

これで速くなるんじゃないかと試したものの逆に遅くなったアイディアもありました。

特化メソッドを持つモジュールをextend

csvにはまじめにパースするモードとゆるくパースするモードがあります。従来はメソッド内でifで分岐していました。インスタンス作成時にモードにあわせたモジュールをextendしてパース時はメソッド内のifを減らすと速くなるのではないか、という案です。こんな感じです。

module StrictMode
  def parse
    # ...
  end
end

module LiberalMode
  def parse
    # ...
  end
end

class CSV::Parser
  def initialize(options)
    if @options[:liberal_mode]
      extend LiberalMode
    else
      extend StrictMode
    end
  end
end

CSV::Parser.new(:liberal_mode).parse # LiberalMode#parse

実際にやってみてところむしろ遅くなりました。メソッド内でifで分岐する方が速かったです。

さらに速いCSVパーサー

csvはRubyレベルで実装してあるCSVパーサーでは最速です。さらに速くするにはCで実装する必要があります。たとえば、Cを使っているfastest-csvはcsvよりも数倍高速です。

なお、私のオススメはApache Arrowです。Apache ArrowはCSV用のライブラリーではありませんが、CSVパーサーもついています。Apache ArrowのCSVパーサーを使うとfastest-csvよりもさらに数倍高速です。

使い方も簡単です。次のコードでCSVをロードできます。

require "arrow"
Arrow::Table.load("/tmp/a.csv")

参考：Apache Arrowの最新情報（2018年9月版）

今後

コードを整理でき、最適化・機能拡張の準備ができました。たとえば、次のような改良をしていきたいです。興味がある人は一緒に開発しましょう。

• バックスラッシュでダブルクォートをエスケープ #61
• クォート文字を指定しなかったらline.split(",")を使う高速化 #56
• ヘッダーがあるときの高速化 #59

まとめ

Ruby 2.6.0にあわせてcsvのコードを整理して高速化しました。より開発しやすいコードベースになったので一緒に開発していきましょう。

リリース直前にいろいろ変更をぶちこんでごめんなさい。

ツイートする

フォローする

Apache Arrow東京ミートアップ2018 - Apache Arrow #ArrowTokyo

Apache Arrow東京ミートアップ2018を主催したした須藤です。会場提供・飲食物提供などSpeeeさんにいろいろ協力してもらいました。ありがとうございます。

私はApache Arrow本体のことを網羅的に紹介しました。データの配置のことなど日本OSS推進フォーラム アプリケーション部会 第10回勉強会では触れなかった技術的な詳細についても紹介しています。

関連リンク：

• スライド（Rabbit Slide Show）
• スライド（SlideShare）
• リポジトリー

集まりの目的

この集まりは勉強会ではありません。勉強をする集まりではなく開発者を増やす集まりです。開発対象のプロダクトはApache Arrowだけでなく、Apache Arrow以外でもデータ処理に関わるプロダクトであればなんでもOKです。

そのため参加枠は次の2つにしました。

• 開発に参加したい気持ちがある枠
• 開発に参加したい気持ちがなくはない枠

開発に参加する気がある人だけが参加する集まりということです。

目的（開発者を増やす）の実現方法

「開発者を増やす」という目的を実現するために時間の使い方を次の2つにわけました。

• 前半：開発を始めるための情報提供の時間
• 後半：開発を始める時間

後半では「開発の1歩目を踏み出せる」ことを目指しました。ポイントは「1歩目」です。この集まりの時間内で「バリバリ開発する」を目指していないということです。この集まりの時間で「なにに取り組もうか」が決まれば十分です。取り組むと決めたことに実際に取り組み始められればなおよしです。

「何に取り組もうか」を決めるために必要そうな情報を前半に提供しました。

前半：開発を始めるための情報提供の時間

前半では、まず私がApache Arrowの関する全体的な情報を提供しました。今回はApache Arrowを軸にいろいろなプロダクトの開発者を増やしたかったので、どのプロジェクトでも参考になりそうな予備知識としてApache Arrowの情報を最初に提供しました。

その後は次のテーマごとに詳しい人から情報を提供しました。適切な人に情報提供してもらえて本当によかったなぁと思っています。

• Apache Spark
  • 資料：Apache Arrow and Pandas UDF on Apache Arrow
  • 情報提供者：上新さん（Apache SparkのコミッターでApache SparkのApache Arrow対応の開発にも参加）
• Multiple-Dimension-Spread
  • 資料：Multiple-Dimension-Spread と Apache Arrow
  • 情報提供者：井島さん（Multiple-Dimension-Spreadの開発者でApache Arrow対応部分も実装）
• R
  • 資料：RとApache Arrow
  • 情報提供者：湯谷さん（日本のR界隈で一番前からApache Arrowのことを調べている）
  • ブログ：Apache Arrow東京ミートアップ2018で「RとApache Arrow」について話してきました - Technically, technophobic.
• Ruby
  • 資料：RubyとApache Arrow
  • 情報提供者：
    • 畑中さん（Red Data ToolsメンバーとしてRuby用のデータ処理ツールを開発）
    • 橋立さん（Ruby用ログ収集基盤のFluentdでApache Arrowを活用するプラグインを開発）
  • ブログ：Apache Arrow東京ミートアップ2018で「RubyとApache Arrow」というタイトルで発表してきました！！！ - hatappi.blog
• Python
  • 資料：PythonとApache Arrow
  • 情報提供者：堀越さん（pandas・Daskのコミッター）
• テンソル
  • 資料：Tensor and Apache Arrow
  • 情報提供者：村田さん（数値計算に詳しくApache Arrowの疎なテンソルを実装中）

みなさんには次の2点を話してくださいとお願いしていました。

• 現状のまとめ
• 今後こうなるとよさそう

「今後こうなるとよさそう」は「開発の1歩目」のヒントになることを期待していました。

私も新しく知ったことが多くあったのでみなさんにお願いして本当によかったなぁと思っています。Rubyまわりを開発している人視点で言うと、特にRとPythonの情報は興味深かったです。RubyでもRのALTREP・pandasのExtensionArrayのようなものが必要になるときは来るのだろうか、とか。

後半：開発を始める時間

前半で開発を始めるための情報を得られたので後半では実際に開発を始める時間です。

次のグループにわかれてグループの人と相談しながら各人が「まずはなにに取り組むか」を決めていきます。

• Apache Arrow（Multiple-Dimension-Spread・Ruby関連を含む）
• Apache Spark
• Python
• R

各グループには詳しい人たちがいるのでその人たちと相談しながら「なにに取り組むか」を決めます。私は各人に「まずはなにに取り組むか決まりましたかー？」と聞いてまわったのですが、だいたいみなさん決められたようでした。最初の1歩を踏み出せましたね。

すでにpull requestを出して2歩目・3歩目を踏み出せている人たちもいるのでいくつかリンクを置いておきますね。

• ARROW-3962: [Go] Support null value while reading CSV #3129
• ARROW-3964: [Go] Refactor examples of csv reader #3131
• ARROW-3961: [Python/Documentation] Fix wrong path in the pyarrow README #3127
• Apache Arrow Meetup行ってきた結果OSS活動の一歩を踏み出した - Diary over Finite Fields

まとめ

勉強会ではなく「開発者を増やす」ことを目的にした集まりを開催しました。この集まりをきっかけに開発に参加した人がいたのでよい集まりだったなぁと思っています。「開発者を増やす」ことを目的にした集まりを開催したい人は参考にしてください。

参加した人たちには集まりの最後にアンケートに答えてもらいました。アンケートの結果はGitHubのspeee/code-party/apache-arrow-tokyo-meetup-2018/feedback/から参照できるので、同様の集まりを開催したい人はこちらも参考にしてください。

引き続き開発に参加していきましょう！

なお、クリアコードはApache Arrowを活用してデータ処理ツールの開発をしたいのでデータ処理ツールを開発していてApache Arrowを活用したい方はお問い合わせください。また、一緒にデータ処理ツールの開発をしたい人も募集しているのでわれこそはという方はご応募ください。

ツイートする

フォローする