check modifcation whil ar->st

* delete `ar_try_convert` but use `ar_force_convert_table`
  to make program simple.
* `ar_force_convert_table` checks hash modification while
  calling `#hash` method with the following strategy:

1. copy keys (and vals) of ar_table
2. calc hashes from keys
3. check copied keys and hash's keys. if not matched, repeat from 1

fix [Bug #20050]

1 files changed, 57 insertions, 42 deletions

diff --git a/hash.c b/hash.c
index 787b824da2..5d210a5e6e 100644
--- a/hash.c
+++ b/hash.c
@@ -694,61 +694,75 @@ hash_ar_free_and_clear_table(VALUE hash)
     HASH_ASSERT(RHASH_AR_TABLE_BOUND(hash) == 0);
 }
 
-static void
-ar_try_convert_table(VALUE hash)
-{
-    if (!RHASH_AR_TABLE_P(hash)) return;
-
-    const unsigned size = RHASH_AR_TABLE_SIZE(hash);
+void rb_st_add_direct_with_hash(st_table *tab, st_data_t key, st_data_t value, st_hash_t hash); // st.c
 
-    if (size < RHASH_AR_TABLE_MAX_SIZE) {
-        return;
-    }
-
-    st_table tab;
-    st_table *new_tab = &tab;
-    rb_st_init_existing_table_with_size(new_tab, &objhash, size * 2);
+enum ar_each_key_type {
+    ar_each_key_copy,
+    ar_each_key_cmp,
+    ar_each_key_insert,
+};
 
-    for (st_index_t i = 0; i < RHASH_AR_TABLE_MAX_BOUND; i++) {
-        ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
-        st_add_direct(new_tab, pair->key, pair->val);
+static inline int
+ar_each_key(ar_table *ar, int max, enum ar_each_key_type type, st_data_t *dst_keys, st_table *new_tab, st_hash_t *hashes)
+{
+    for (int i = 0; i < max; i++) {
+        ar_table_pair *pair = &ar->pairs[i];
+
+        switch (type) {
+          case ar_each_key_copy:
+            dst_keys[i] = pair->key;
+            break;
+          case ar_each_key_cmp:
+            if (dst_keys[i] != pair->key) return 1;
+            break;
+          case ar_each_key_insert:
+            if (UNDEF_P(pair->key)) continue; // deleted entry
+            rb_st_add_direct_with_hash(new_tab, pair->key, pair->val, hashes[i]);
+            break;
+        }
     }
 
-    hash_ar_free_and_clear_table(hash);
-    RHASH_ST_TABLE_SET(hash, new_tab);
+    return 0;
 }
 
 static st_table *
 ar_force_convert_table(VALUE hash, const char *file, int line)
 {
-    st_table *new_tab;
-    st_table tab;
-    new_tab = &tab;
-
     if (RHASH_ST_TABLE_P(hash)) {
         return RHASH_ST_TABLE(hash);
     }
+    else {
+        ar_table *ar = RHASH_AR_TABLE(hash);
+        st_hash_t hashes[RHASH_AR_TABLE_MAX_SIZE];
+        unsigned int bound, size;
+
+        // prepare hash values
+        do {
+            st_data_t keys[RHASH_AR_TABLE_MAX_SIZE];
+            bound = RHASH_AR_TABLE_BOUND(hash);
+            size = RHASH_AR_TABLE_SIZE(hash);
+            ar_each_key(ar, bound, ar_each_key_copy, keys, NULL, NULL);
+
+            for (unsigned int i = 0; i < bound; i++) {
+                // do_hash calls #hash method and it can modify hash object
+                hashes[i] = UNDEF_P(keys[i]) ? 0 : ar_do_hash(keys[i]);
+            }
 
-    RUBY_ASSERT(RHASH_AR_TABLE(hash));
-    {
-        unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
-
-        rb_st_init_existing_table_with_size(new_tab, &objhash, RHASH_AR_TABLE_SIZE(hash));
-
-        for (i = 0; i < bound; i++) {
-            if (ar_cleared_entry(hash, i)) continue;
-
-            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
-            st_add_direct(new_tab, pair->key, pair->val);
-        }
+            // check if modified
+            if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) return RHASH_ST_TABLE(hash);
+            if (UNLIKELY(RHASH_AR_TABLE_BOUND(hash) != bound)) continue;
+            if (UNLIKELY(ar_each_key(ar, bound, ar_each_key_cmp, keys, NULL, NULL))) continue;
+        } while (0);
+
+        // make st
+        st_table tab;
+        st_table *new_tab = &tab;
+        rb_st_init_existing_table_with_size(new_tab, &objhash, size);
+        ar_each_key(ar, bound, ar_each_key_insert, NULL, new_tab, hashes);
         hash_ar_free_and_clear_table(hash);
+        RHASH_ST_TABLE_SET(hash, new_tab);
+        return RHASH_ST_TABLE(hash);
     }
-
-    RHASH_ST_TABLE_SET(hash, new_tab);
-
-    new_tab = RHASH_ST_TABLE(hash);
-
-    return new_tab;
 }
 
 static int
@@ -1638,7 +1652,7 @@ rb_hash_stlike_update(VALUE hash, st_data_t key, st_update_callback_func *func,
     if (RHASH_AR_TABLE_P(hash)) {
         int result = ar_update(hash, key, func, arg);
         if (result == -1) {
-            ar_try_convert_table(hash);
+            ar_force_convert_table(hash, __FILE__, __LINE__);
         }
         else {
             return result;
@@ -4704,8 +4718,9 @@ rb_hash_add_new_element(VALUE hash, VALUE key, VALUE val)
         if (ret != -1) {
             return ret;
         }
-        ar_try_convert_table(hash);
+        ar_force_convert_table(hash, __FILE__, __LINE__);
     }
+
     tbl = RHASH_TBL_RAW(hash);
     return st_update(tbl, (st_data_t)key, add_new_i, (st_data_t)args);