From: masa <masap.hat@...>
Date: 2011-01-26T08:09:41+09:00
Subject: [ruby-dev:43111] Hashのイテレーション中の新規キー追加

ruby-list の方で同じタイトルで投稿した畠山です。
(ruby-list:47766)

ruby-dev 初投稿になり、勝手がよくわかっていませんが、
どうぞよろしくお願いします。

問題点
Ruby 1.8.7 においてHashイテレーション中に自己のHashに
キーを追加していくとある一定数以上のところでRuntimeError
になる。これを常に新しくキーを追加できるようにできないか。

より具体的には、
遠藤さんから提示してもらった

  h = {}
  (1..66).each {|n| h[n.to_s] = n }
  h.each_key do |k|
    p k
    if k == '66'
      h['67'] = 67
    end
  end

が Ruby 1.8.7 でエラーになるのを解決したい、というのが
いま私のやりたいことです。（そもそもそんなの必要ない、
ということでしたらそもそも議論の余地はありませんが...）

その後、ハッシュのソースコード(Ruby-1.8.7-p330, st.c, hash.c)を
読ませてもらいまして、おおよそ理解しました。
（Ruby 1.9 のハッシュコードはまだ読んでいません）

まず問題点の整理ですが（Ruby1.8.7においてですが）
Hashイテレーション中に新規キーを追加したときにエラーが
起きるのは、

(st.c内において)
キーを追加中にHash密度が一定値を超えるとrehash関数が
呼ばれ、table->binsがcallocされ直すためにst_foreach関数内
のptrポインタ変数の指し示す場所が不明になってしまうこと
からエラーになる、という処理だということを理解しました。

その後、よくよくst_foreach関数（st.c）を眺めてみまして
（この関数が自体の意義はまだ完全に理解できていませんが）
ptrの行き先が不明になったところで代入し直してあげることで
とりえあず上記のサンプルのエラーは回避することができました。
ただ、st_foreach関数のcase ST_CHECKはrehashに伴うtable->bins
変更チェック以外の役割もある気がするので、その場合には
まずいかもしれないと思っています。
か、もしくは、まだ私の理解が浅いので、根本的に「それはまずい」
という場合がありましたら、どなたかアドバイスをお願いします。

一応 make test はパスしましたがmake test-all は二つほどFailure
がでました（その失敗はまだ追えてません）。

以下 diff -u の結果を添付します。

--- st.c.org	2011-01-25 23:46:02.000000000 +0100
+++ st.c	2011-01-25 23:44:06.000000000 +0100
@@ -495,7 +495,8 @@
 		}
 		if (!tmp) {
 		    /* call func with error notice */
-		    return 1;
+		    /*return 1;*/
+		    ptr = table->bins[i];
 		}
 		/* fall through */
 	    case ST_CONTINUE:

この方向性でもし問題がないようでしたら
（もしくはプラスアルファで問題が解決しそうなら）
Ruby1.9.2のコードも眺めてみたいと思います。
がそもそも根本的にまずいという場合は出直すことにします。

それからいまいち Wiki の使い方がわかっていないのですが、こう
いう問題提起をしたい場合はどういう手順を踏むのが良いでしょうか？

長々すいませんでしたが、どうぞよろしくお願いします。
畠山