Custom queries

Backport 3.2
Backport 3.3
Backport 3.4
bugs: unassigned
DevMeeting
matz
Open issues with attachment
Windows

Actions

Copy link

Bug #1107

closed

lack consistency in hash iteration

Added by mame (Yusuke Endoh) over 16 years ago. Updated about 14 years ago.

Status:

Closed

Assignee:

Target version:

ruby -v:

Backport:

[ruby-dev:37910]

Description

=begin
遠藤です。

[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 }'

は無限ループになります。
直感的にはどちらも無限ループになると思いました。

特に反対がなければ、以下のパッチをコミットしようと思います。

Index: st.c¶

--- st.c (revision 22051)
+++ st.c (working copy)
@@ -653,6 +653,7 @@
do {
end = ptr->fore == table->head;
retval = (*func)(ptr->key, ptr->record, arg);

 end = end && (ptr->fore == table->head);
 switch (retval) {
   case ST_CHECK:	/* check if hash is modified during iteration */
 i = ptr->hash % table->num_bins;

Index: test/ruby/test_hash.rb¶

--- test/ruby/test_hash.rb (revision 22051)
+++ test/ruby/test_hash.rb (working copy)
@@ -849,4 +849,30 @@
def test_hash_hash
assert_equal({0=>2,11=>1}.hash, {11=>1,0=>2}.hash)
end
+

def test_iteration_order
h = {1=>nil,3=>nil,2=>nil,4=>nil}
assert_equal([1, 3, 2, 4], h.each_key.to_a)
h.each_key {|k| h[k + 10] = nil if h.size < 8 }
assert_equal([1, 3, 2, 4, 11, 13, 12, 14], h.each_key.to_a)
h = {0=>nil}
i = 1
h.each_key do |k|
```
 break if h.size == 5
```
```
 h[i] = nil
```
```
 i += 1
```
end
assert_equal({0=>nil,1=>nil,2=>nil,3=>nil,4=>nil}, h)
h = {0=>nil,1=>nil}
i = 2
h.each_key do |k|
```
 break if h.size == 5
```
```
 h[i] = nil
```
```
 i += 1
```
end
assert_equal({0=>nil,1=>nil,2=>nil,3=>nil,4=>nil}, h)
end
end

--
Yusuke ENDOH [email protected]
=end

History
Notes
Property changes

Actions

Copy link

Updated by matz (Yukihiro Matsumoto) over 16 years ago

=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

Actions

Copy link

Updated by mame (Yusuke Endoh) over 16 years ago

=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

Actions

Copy link

Updated by matz (Yukihiro Matsumoto) over 16 years ago

=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:

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

=end

Actions

Copy link

Updated by mame (Yusuke Endoh) over 16 years ago

=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

Actions

Copy link

Updated by mame (Yusuke Endoh) over 16 years ago

=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

Actions

Copy link

Updated by mame (Yusuke Endoh) over 16 years ago

Status changed from Open to Closed
% Done changed from 0 to 100

=begin
Applied in changeset r22132.
=end

Actions

Copy link

Also available in: Atom PDF

Like0

Like0Like0Like0Like0Like0Like0

Project

General

Profile

Ruby

Tags

Custom queries

Bug #1107

lack consistency in hash iteration

Index: st.c¶

Index: test/ruby/test_hash.rb¶

Updated by matz (Yukihiro Matsumoto) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Updated by matz (Yukihiro Matsumoto) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Index: include/ruby/st.h¶

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

Updated by mame (Yusuke Endoh) over 16 years ago

Project

General

Profile

Ruby

Tags

Custom queries

Bug #1107

lack consistency in hash iteration

Index: st.c¶

Index: test/ruby/test_hash.rb¶

Updated by matz (Yukihiro Matsumoto) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Updated by matz (Yukihiro Matsumoto) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Updated by mame (Yusuke Endoh) over 16 years ago

Index: include/ruby/st.h¶

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

Updated by mame (Yusuke Endoh) over 16 years ago

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