本記事はOpal Advent Calendar 2016の19日目のエントリです。

今回はOpalのHashクラスの実装について見ていきます。

corelib/runtime.js

opal/corelibは、array.rbやstring.rbなど、組み込みクラスの実装が置かれているディレクトリです。この中に一つだけ、runtime.jsという、拡張子が.jsのファイルがあります。

runtime.jsはコンパイル後のJavaScriptの一部としてそのまま埋め込まれます。クラスの生成や 定数の探索といった処理系の基礎となる機能が実装されており、Opalの心臓部といえるでしょう。

Opal.hash_xx

runtime.jsでは、ハッシュを扱う以下のような関数が定義されています。

• Opal.hash_init
• Opal.hash_clone
• Opal.hash_put
• Opal.hash_get
• Opal.hash_delete
• Opal.hash_rehash
• Opal.hash
• Opal.hash2

hash_getやhash_putを眺めてみると、ハッシュアルゴリズムを自前で実装していることが分かります。

単純な、文字列だけをキーとするハッシュであればJavaScriptのオブジェクトにそのままマップできるかもしれませんが、RubyのHashクラスは任意のRubyオブジェクトをキーにできたり、ハッシュ値を明示できたりするため、このようになっています。

Hashクラスとの関係

Hashクラスはopal/corelib/hash.rbで定義されています。これを見ると、Hashクラスのメソッドは先ほどのhash_getやhash_putを使って実装されていることが分かります。

以下はHash#[]=メソッドの定義です。単純にhash_putを呼ぶだけですね。

  def []=(key, value)
    %x{
      Opal.hash_put(self, key, value);
      return value;
    }
  end

Hash#[]の方も見てみましょう。こちらもほぼhash_getを呼ぶだけですが、値が存在しなかったときはdefaultメソッドを呼ぶようになっています(mrubyのアドカレ記事でもこの話しましたね)。

  def [](key)
    %x{
      var value = Opal.hash_get(self, key);
      if (value !== undefined) {
        return value;
      }
      return self.$default(key);
    }
  end

各関数とメソッドの対応をまとめておきます。

• Opal.hash_init : Hash.newやHash#clearから呼ばれる
• Opal.hash_clone : Hash#cloneやHash#to_hから呼ばれる
• Opal.hash_put : Hash#[]=などから呼ばれる
• Opal.hash_get : Hash#[]などから呼ばれる
• Opal.hash_delete : Hash#deleteやHash#reject!などから呼ばれる
• Opal.hash_rehash : Hash#rehashから呼ばれる
• Opal.hash : 空のハッシュを作る。Hash#selectやHash#rejectなどから呼ばれる
• Opal.hash2 : キーがString/Symbolのハッシュを作る。Opal.hashより速い。Hashクラスでは使っていないが、処理系の他の箇所(キーワード引数の実装など)で使っている

ハッシュオブジェクトの実装

Opal.hash_xxの実装も少し見てみましょう。まず、ハッシュオブジェクトは以下のプロパティを持つことが分かります。

  Opal.hash_init = function(hash) {
    hash.$$smap = {};
    hash.$$map  = {};
    hash.$$keys = [];
  };

$$smapと$$mapが、キーと値の組を保持します。RubyのハッシュのキーはたいていStringかSymbolなので、キーが文字列のときは$$smapを使い、そうでないときだけ$$mapを使うようです。(OpalではSymbolはStringと同じものです)

$$keysはキーの一覧を高速化のためキャッシュしたもので、Hash#keysメソッド等で使われます。またこのプロパティを見ればハッシュのサイズが分かるため、Hash#lengthの実装にも使われています。

  def length
    `self.$$keys.length`
  end

ハッシュテーブルの実装

最後に、ハッシュテーブルの実装を確認するため、Opal.hash_putを見てみましょう。

キーが文字列のときは、$$smapをハッシュテーブル代わりにして値を格納するだけです。

    if (key.$$is_string) {
      if (!hash.$$smap.hasOwnProperty(key)) {
        hash.$$keys.push(key);
      }
      hash.$$smap[key] = value;
      return;
    }

キーが文字列でない場合は、Object#hashメソッドを実行してハッシュ値(key_hash)を得ます。これを使ってキーと値のペアを格納するのですが、ハッシュ値は衝突する可能性があるため注意が必要です。

    var key_hash = key.$hash(), bucket, last_bucket;

まず、衝突が起こらなかった場合です。$$mapにハッシュ値がkey_hashであるオブジェクトが格納されていない場合は、新しいbucketを作って保存します。bucketは生のキーと値を保持するJSオブジェクトで、ここには出てきていないですがもう一つnextというプロパティがあり、要するにリンクドリストになっています。

    if (!hash.$$map.hasOwnProperty(key_hash)) {
      bucket = {key: key, key_hash: key_hash, value: value};
      hash.$$keys.push(bucket);
      hash.$$map[key_hash] = bucket;
      return;
    }

衝突が起こった場合、つまり当該ハッシュ値のbucketが既に存在する場合は、各bucketの中身を調べます。キーが一致する(Object#eql?)ものがあれば、このキーに対する値を上書きしようとしているわけなので、bucket.valueを更新します。

    bucket = hash.$$map[key_hash];

    while (bucket) {
      if (key === bucket.key || key['$eql?'](bucket.key)) {
        last_bucket = undefined;
        bucket.value = value;
        break;
      }
      last_bucket = bucket;
      bucket = bucket.next;
    }

上書きでなかった場合は、最終的にbucket.nextがundefinedになるのでループを抜けます。このとき、一番最後のbucketを覚えておきます(last_bucket)。新しいbucketを作り、last_bucketの後ろに連結します。

    if (last_bucket) {
      bucket = {key: key, key_hash: key_hash, value: value};
      hash.$$keys.push(bucket);
      last_bucket.next = bucket;
    }

以上でOpal.hash_putの実装は終わりです。

まとめ

• 任意のRubyオブジェクトをキーにできるようにするため、ハッシュテーブルを自前で実装している
• キーがString/SymbolのときはJSオブジェクトを使う
• Hashのメソッドの実装はOpal.hash_xxを呼んでいる