Bug #9646

Infinite loop at Hash#each

Added by Masaya Tarui about 1 year ago. Updated 9 months ago.

[ruby-dev:48047]
Status:Closed
Priority:Normal
Assignee:-
ruby -v:ruby 2.0.0p291 (2013-08-11 revision 42493) [x86_64-linux] Backport:2.0.0: DONE, 2.1: DONE

Description

Hashでキーを同じにすると、無限ループしてしまいます。

再現コードは
ruby -e 'h={};h[a=[]]=1;a<<1;h[[]] = 2;a.clear;h.each{|i| p i}'
です。

st_foreach_checkcallcc対応のために
find_packed_indexを毎回呼んでおり、そこでiが進まなくなっています。
そもそも、同じキーの状態を作り出せるのがどうなんだという話はあるかもしれませんが、
そちらを直すのは大きな変更になりそうなので、とりあえず以下のような感じでどうでしょうか?
callccでの後戻りをあきらめています。

#または、callccでイテレータの中に戻るのを禁止した方がよいのかもしれません。

--- a/st.c
+++ b/st.c
@@ -394,9 +394,8 @@ find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_p
 }

 static inline st_index_t
-find_packed_index(st_table *table, st_index_t hash_val, st_data_t key)
+find_packed_index_from(st_table *table, st_index_t hash_val, st_data_t key,st_index_t i)
 {
-    st_index_t i = 0;
     while (i < table->real_entries &&
           (PHASH(table, i) != hash_val || !EQUAL(table, key, PKEY(table, i)))) {
        i++;
@@ -404,6 +403,12 @@ find_packed_index(st_table *table, st_index_t hash_val, st_data_t key)
     return i;
 }

+static inline st_index_t
+find_packed_index(st_table *table, st_index_t hash_val, st_data_t key)
+{
+    return find_packed_index_from(table,hash_val,key,0);
+}
+
 #define collision_check 0

 int
@@ -963,8 +968,8 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t
                if (PHASH(table, i) == 0 && PKEY(table, i) == never) {
                    break;
                }
-               i = find_packed_index(table, hash, key);
-               if (i == table->real_entries) {
+               i = find_packed_index_from(table, hash, key, i);
+               if (i >= table->real_entries) {
                    goto deleted;
                }
                /* fall through */

Related issues

Duplicated by Ruby trunk - Bug #9729: Hash#each が無限ループする Closed 04/11/2014

Associated revisions

Revision 45642
Added by Masaya Tarui 11 months ago

  • st.c (st_foreach_check): chnage start point of search at check from top to current. [Bug #9646]

Revision 45642
Added by Masaya Tarui 11 months ago

  • st.c (st_foreach_check): chnage start point of search at check from top to current. [Bug #9646]

Revision 46721
Added by Tomoyuki Chikanaga 9 months ago

merge revision(s) r45642,r45643: [Backport #9646] [Backport #9729]

* st.c (st_foreach_check): chnage start point of search at check
  from top to current.  [Bug #9646]

* st.c (st_foreach_check): change start point of search at check

Revision 46747
Added by Usaku NAKAMURA 9 months ago

merge revision(s) 45642,45643: [Backport #9646] [Backport #9729]

* st.c (st_foreach_check): chnage start point of search at check
  from top to current.  [Bug #9646]

* st.c (st_foreach_check): change start point of search at check

History

#1 Updated by Nobuyoshi Nakada about 1 year ago

  • Description updated (diff)

#2 Updated by Nobuyoshi Nakada 12 months ago

  • Duplicated by Bug #9729: Hash#each が無限ループする added

#3 Updated by Masaya Tarui 11 months ago

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

Applied in changeset r45642.


  • st.c (st_foreach_check): chnage start point of search at check from top to current. [Bug #9646]

#4 Updated by Usaku NAKAMURA 9 months ago

  • Backport changed from 2.0.0: UNKNOWN, 2.1: UNKNOWN to 2.0.0: REQUIRED, 2.1: REQUIRED

#5 Updated by Tomoyuki Chikanaga 9 months ago

  • Backport changed from 2.0.0: REQUIRED, 2.1: REQUIRED to 2.0.0: REQUIRED, 2.1: DONE

Backported into ruby_2_1 branch at r46721.

#6 Updated by Usaku NAKAMURA 9 months ago

  • Backport changed from 2.0.0: REQUIRED, 2.1: DONE to 2.0.0: DONE, 2.1: DONE

backported into ruby_2_0_0 at r46747.

Also available in: Atom PDF