=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:37910] [Bug:1.9] lack consistency in hash iteration"
on Thu, 5 Feb 2009 02:51:16 +0900, Yusuke ENDOH [email protected] writes:

|[ruby-core:21812] で調べていて気が付いたことですが、
|
|$ ./ruby -e 'h = {0 => nil}; i = 1; h.each_key { h[i] = nil; i += 1 }'
|
|は停止し、
|
|$ ./ruby -e 'h = {0 => nil, 1 => nil}; i = 2; h.each_key { h[i] = nil; i += 1 }'
|
|は無限ループになります。
|直感的にはどちらも無限ループになると思いました。

手抜きで申し訳ないのですが、以下の点について教えてください。

• このパッチの対象は1.9ですか、1.8ですか？
• このパッチを当てると両方とも無限ループになりますか？

=end

=begin
遠藤です。

2009/02/05 3:11 Yukihiro Matsumoto [email protected]:

まつもと ゆきひろです

In message "Re: [ruby-dev:37910] [Bug:1.9] lack consistency in hash iteration"
on Thu, 5 Feb 2009 02:51:16 +0900, Yusuke ENDOH [email protected] writes:

|[ruby-core:21812] で調べていて気が付いたことですが、
|
|$ ./ruby -e 'h = {0 => nil}; i = 1; h.each_key { h[i] = nil; i += 1 }'
|
|は停止し、
|
|$ ./ruby -e 'h = {0 => nil, 1 => nil}; i = 2; h.each_key { h[i] = nil; i += 1 }'
|
|は無限ループになります。
|直感的にはどちらも無限ループになると思いました。

手抜きで申し訳ないのですが、以下の点について教えてください。

こちらこそ説明不足で申し訳ありません。

• このパッチの対象は1.9ですか、1.8ですか？

[Bug:1.9] のとおり、1.9 用です。

• このパッチを当てると両方とも無限ループになりますか？

はい、両方とも無限ループになります。

あと私の環境で make check は通っています。

よろしくお願いします。

--
Yusuke ENDOH [email protected]

=end

=begin
まつもと ゆきひろです

In message "Re: [ruby-dev:37912] Re: [Bug:1.9] lack consistency in hash iteration"
on Thu, 5 Feb 2009 03:18:19 +0900, Yusuke ENDOH [email protected] writes:

|> * このパッチの対象は1.9ですか、1.8ですか？
|
|[Bug:1.9] のとおり、1.9 用です。
|
|> * このパッチを当てると両方とも無限ループになりますか？
|
|はい、両方とも無限ループになります。
|
|あと私の環境で make check は通っています。

いいんじゃないでしょうか。コミットしてください。

=end

=begin
遠藤です。

2009/02/05 3:25 Yukihiro Matsumoto [email protected]:

まつもと ゆきひろです

In message "Re: [ruby-dev:37912] Re: [Bug:1.9] lack consistency in hash iteration"
on Thu, 5 Feb 2009 03:18:19 +0900, Yusuke ENDOH [email protected] writes:

|> * このパッチの対象は1.9ですか、1.8ですか？
|
|[Bug:1.9] のとおり、1.9 用です。
|
|> * このパッチを当てると両方とも無限ループになりますか？
|
|はい、両方とも無限ループになります。
|
|あと私の環境で make check は通っています。

いいんじゃないでしょうか。コミットしてください。

すみません、まだコミットしてないんですが、このパッチにはバグがありました。
同じ要素を複数回 yield する可能性があります。

$ ./ruby -e 'h = {1=>1,2=>2}; h.each {|x| p x; h.delete(2) }'
[1, 1]
[1, 1]

すぐには解決策が思いつかないので、ちょっと考えます。

--
Yusuke ENDOH [email protected]

=end

=begin
遠藤です。

2009/02/06 1:01 Yusuke ENDOH [email protected]:

同じ要素を複数回 yield する可能性があります。

$ ./ruby -e 'h = {1=>1,2=>2}; h.each {|x| p x; h.delete(2) }'
[1, 1]
[1, 1]

すぐには解決策が思いつかないので、ちょっと考えます。

現状の st_foreach だと、Hash のイテレート中にハッシュの要素を削除すると
削除されていない要素でも取りこぼすことがあるようです。

a = (1..3).map do |i|
x = Object.new
def x.hash; 1; end
x
end

h = {}
a.each {|x| h[x] = true }

p h #=> {#Object:0x81fcdb0=>true, #Object:0x81fcce8=>true,
#Object:0x81fcc5c=>true}

h.each do |x|
p x
h.delete(a[0])
h.delete(a[1])
end
#=> [#Object:0x81fcdb0, true] だけしか出ない、[#Object:0x81fcc5c=>true, true] は出るはず

p h #=> {#Object:0x81fcc5c=>true}

原因はイテレートの終了条件が正しくないためですが、Hash の順序を
ループ構造で管理している限り解決できないような気がしました。

順序を双方向リストで管理すれば直りました。

Index: include/ruby/st.h¶

--- include/ruby/st.h (revision 22101)
+++ include/ruby/st.h (working copy)
@@ -75,7 +75,7 @@
#endif
st_index_t num_entries : ST_INDEX_BITS - 1;
struct st_table_entry **bins;

• struct st_table_entry *head;

• struct st_table_entry *head, *back;
  };

#define st_is_member(table,key) st_lookup(table,key,(st_data_t *)0)
Index: st.c¶

--- st.c (revision 22101)
+++ st.c (working copy)
@@ -176,6 +176,7 @@
tbl->num_bins = size;
tbl->bins = (st_table_entry *)Calloc(size, sizeof(st_table_entry));
tbl->head = 0;

• tbl->back = 0;

  return tbl;
  }
  @@ -244,6 +245,7 @@
  }
  table->num_entries = 0;
  table->head = 0;

• table->back = 0;
  }

void
@@ -335,7 +337,7 @@

#define ADD_DIRECT(table, key, value, hash_val, bin_pos)
do {\

• st_table_entry *entry, *head;\

• st_table_entry *entry;
  if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {
  rehash(table);
  bin_pos = hash_val % table->num_bins;
  @@ -347,13 +349,14 @@
  entry->key = key;
  entry->record = value;
  entry->next = table->bins[bin_pos];\

• if ((head = table->head) != 0) {\
• entry->fore = head;\
• (entry->back = head->back)->fore = entry;\
• head->back = entry;\

• if (table->head != 0) {\
• entry->fore = 0;\
• (entry->back = table->back)->fore = entry;\
• table->back = entry;
  }
  else {\

• table->head = entry->fore = entry->back = entry;\

• table->head = table->back = entry;\
• entry->fore = entry->back = 0;
  }
  table->bins[bin_pos] = entry;
  table->num_entries++;
  @@ -455,7 +458,7 @@
  hash_val = ptr->hash % new_num_bins;
  ptr->next = new_bins[hash_val];
  new_bins[hash_val] = ptr;

• } while ((ptr = ptr->fore) != table->head);

• } while ((ptr = ptr->fore) != 0);
  }
  }

@@ -502,10 +505,8 @@
entry->back = prev;
*tail = prev = entry;
tail = &entry->fore;

• } while ((ptr = ptr->fore) != old_table->head);
• entry = new_table->head;
• entry->back = prev;
• *tail = entry;

• } while ((ptr = ptr->fore) != 0);

• new_table->back = prev;
  }

  return new_table;
  @@ -513,14 +514,16 @@

#define REMOVE_ENTRY(table, ptr) do
{ \

• if (ptr == ptr->fore) { \

• if (ptr->fore == 0 && ptr->back == 0) {
  table->head = 0; \

•  table->back = 0;						\
  

  }
  else {
  st_table_entry *fore = ptr->fore, *back = ptr->back; \

•  fore->back = back;						\
  

•  back->fore = fore;						\
  

•  if (fore) fore->back = back;				\
  

•  if (back) back->fore = fore;				\
   if (ptr == table->head) table->head = fore;			\
  

•  if (ptr == table->back) table->back = back;			\
  

  }
  table->num_entries--;
  } while (0)
  @@ -613,7 +616,7 @@
  {
  st_table_entry *ptr, **last, *tmp;
  enum st_retval retval;

• int i, end;

• int i;

  if (table->entries_packed) {
  for (i = 0; i < table->num_entries; i++) {
  @@ -651,7 +654,6 @@

  if ((ptr = table->head) != 0) {
  do {

•  end = ptr->fore == table->head;
   retval = (*func)(ptr->key, ptr->record, arg);
   switch (retval) {
     case ST_CHECK:	/* check if hash is modified during iteration */
  

@@ -683,7 +685,7 @@
}
}
}

• } while (!end && table->head);

• } while (ptr && table->head);
  }
  return 0;
  }
  @@ -694,7 +696,7 @@
  {
  st_table_entry *ptr, **last, *tmp;
  enum st_retval retval;

• int i, end;

• int i;

  if (table->entries_packed) {
  for (i = table->num_entries-1; 0 <= i; i--) {
  @@ -732,7 +734,6 @@
  if ((ptr = table->head) != 0) {
  ptr = ptr->back;
  do {

•  end = ptr == table->head;
   retval = (*func)(ptr->key, ptr->record, arg, 0);
   switch (retval) {
     case ST_CHECK:	/* check if hash is modified during iteration */
  

@@ -766,7 +767,7 @@
free(tmp);
table->num_entries--;
}

• } while (!end && table->head);

• } while (ptr && table->head);
  }
  return 0;
  }

--
Yusuke ENDOH [email protected]

=end