[Bug:1.9] lack consistency in hash iteration


#1

e$B1sF#$G$9!#e(B

[ruby-core:21812] e$B$GD4$Y$F$$$F5$$,IU$$$?$3$H$G$9$,!"e(B

$ ./ruby -e ‘h = {0 => nil}; i = 1; h.each_key { h[i] = nil; i += 1 }’

e$B$ODd;_$7!"e(B

$ ./ruby -e ‘h = {0 => nil, 1 => nil}; i = 2; h.each_key { h[i] = nil; i
+= 1 }’

e$B$OL58B%k!<%W$K$J$j$^$9!#e(B
e$BD>46E*$K$O$I$A$i$bL58B%k!<%W$K$J$k$H;W$$$^$7$?!#e(B

e$BFC$KH?BP$,$J$1$l$P!"0J2<$N%Q%C%A$r%3%_%C%H$7$h$&$H;W$$$^$9!#e(B

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

#2

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

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 removed_email_address@domain.invalid
writes:

|[ruby-core:21812] e$B$GD4$Y$F$$$F5$$,IU$$$?$3$H$G$9$,!"e(B
|
|$ ./ruby -e ‘h = {0 => nil}; i = 1; h.each_key { h[i] = nil; i += 1 }’
|
|e$B$ODd;_$7!"e(B
|
|$ ./ruby -e ‘h = {0 => nil, 1 => nil}; i = 2; h.each_key { h[i] = nil; i += 1 }’
|
|e$B$OL58B%k!<%W$K$J$j$^$9!#e(B
|e$BD>46E*$K$O$I$A$i$bL58B%k!<%W$K$J$k$H;W$$$^$7$?!#e(B

e$B<jH4$-$G?=$7Lu$J$$$N$G$9$,!"0J2<$NE@$K$D$$$F65$($F$/$@$5$$!#e(B

  • e$B$3$N%Q%C%A$NBP>]$Oe(B1.9e$B$G$9$+!"e(B1.8e$B$G$9$+!)e(B
  • e$B$3$N%Q%C%A$rEv$F$k$HN>J}$H$bL58B%k!<%W$K$J$j$^$9$+!)e(B

#3

e$B1sF#$G$9!#e(B

2009/02/05 3:11 Yukihiro M. removed_email_address@domain.invalid:

|
|$ ./ruby -e ‘h = {0 => nil, 1 => nil}; i = 2; h.each_key { h[i] = nil; i += 1 }’
|
|e$B$OL58B%k!<%W$K$J$j$^$9!#e(B
|e$BD>46E*$K$O$I$A$i$bL58B%k!<%W$K$J$k$H;W$$$^$7$?!#e(B

e$B<jH4$-$G?=$7Lu$J$$$N$G$9$,!"0J2<$NE@$K$D$$$F65$($F$/$@$5$$!#e(B

e$B$3$A$i$3$=@bL@ITB-$G?=$7Lu$"$j$^$;$s!#e(B

  • e$B$3$N%Q%C%A$NBP>]$Oe(B1.9e$B$G$9$+!"e(B1.8e$B$G$9$+!)e(B

[Bug:1.9] e$B$N$H$*$j!"e(B1.9 e$BMQ$G$9!#e(B

  • e$B$3$N%Q%C%A$rEv$F$k$HN>J}$H$bL58B%k!<%W$K$J$j$^$9$+!)e(B

e$B$O$$!"N>J}$H$bL58B%k!<%W$K$J$j$^$9!#e(B

e$B$"$H;d$N4D6-$Ge(B make check e$B$ODL$C$F$$$^$9!#e(B

e$B$h$m$7$/$*4j$$$7$^$9!#e(B


#4

e$B1sF#$G$9!#e(B

2009/02/05 3:25 Yukihiro M. removed_email_address@domain.invalid:

|
|e$B$O$$!“N>J}$H$bL58B%k!<%W$K$J$j$^$9!#e(B
|
|e$B$”$H;d$N4D6-$Ge(B make check e$B$ODL$C$F$$$^$9!#e(B

e$B$$$$$s$8$c$J$$$G$7$g$&$+!#%3%_%C%H$7$F$/$@$5$$!#e(B

e$B$9$$^$;$s!"$^$@%3%%C%H$7$F$J$$$s$G$9$,!"$3$N%Q%C%A$K$O%P%0$,$"$j$^$7$?!#e(B
e$BF1$8MWAG$rJ#?t2se(B yield e$B$9$k2DG=@-$,$"$j$^$9!#e(B

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

e$B$9$0$K$O2r7h:v$,;W$$$D$+$J$$$N$G!"$A$g$C$H9M$($^$9!#e(B


#5

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

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 removed_email_address@domain.invalid
writes:

|> * e$B$3$N%Q%C%A$NBP>]$Oe(B1.9e$B$G$9$+!"e(B1.8e$B$G$9$+!)e(B
|
|[Bug:1.9] e$B$N$H$*$j!"e(B1.9 e$BMQ$G$9!#e(B
|
|> * e$B$3$N%Q%C%A$rEv$F$k$HN>J}$H$bL58B%k!<%W$K$J$j$^$9$+!)e(B
|
|e$B$O$$!“N>J}$H$bL58B%k!<%W$K$J$j$^$9!#e(B
|
|e$B$”$H;d$N4D6-$Ge(B make check e$B$ODL$C$F$$$^$9!#e(B

e$B$$$$$s$8$c$J$$$G$7$g$&$+!#%3%_%C%H$7$F$/$@$5$$!#e(B


#6

e$B%A%1%C%He(B #1107 e$B$,99?7$5$l$^$7$?!#e(B (by Yusuke E.)

e$B%9%F!<%?%9e(B Opene$B$+$ie(BClosede$B$KJQ99e(B
e$B?JD=e(B % 0e$B$+$ie(B100e$B$KJQ99e(B

Applied in changeset r22132.

http://redmine.ruby-lang.org/issues/show/1107


#7

e$B1sF#$G$9!#e(B

2009/02/06 1:01 Yusuke ENDOH removed_email_address@domain.invalid:

e$BF1$8MWAG$rJ#?t2se(B yield e$B$9$k2DG=@-$,$"$j$^$9!#e(B

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

e$B$9$0$K$O2r7h:v$,;W$$$D$+$J$$$N$G!"$A$g$C$H9M$($^$9!#e(B

e$B8=>u$Ne(B st_foreach e$B$@$H!“e(BHash
e$B$N%$%F%l!<%HCf$K%O%C%7%e$NMWAG$r:o=|$9$k$He(B
e$B:o=|$5$l$F$$$J$$MWAG$G$b<h$j$3$$9$3$H$,$”$k$h$&$G$9!#e(B

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]
e$B$@$1$7$+=P$J$$!"e(B[#Object:0x81fcc5c=>true, true] e$B$O=P$k$O$:e(B

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

e$B860x$O%$%F%l!<%H$N=*N;>r7o$,@5$7$/$J$$$?$a$G$9$,!"e(BHash
e$B$N=g=x$re(B
e$B%k!<%W9=B$$G4IM}$7$F$$$k8B$j2r7h$G$-$J$$$h$&$J5$$,$7$^$7$?!#e(B

e$B=g=x$rAPJ}8~%j%9%H$G4IM}$9$l$PD>$j$^$7$?!#e(B

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;
    }