From f2d8db39be487fcd710c5c5844ae47d3a6920e70 Mon Sep 17 00:00:00 2001 From: KOBAYASHI Shuji Date: Tue, 10 Nov 2020 14:02:55 +0900 Subject: Reduce memory usage of Hash object ## Implementation Summary * Change entry list from segmented list to flat array. * Change value of hash bucket from pointer to entry to index of entry list, and represent it by variable length bits according to capacity of hash buckets. * Store management information about entry list and hash table to `struct RHash` as much as possible. ## Benchmark Summary Only the results of typical situations on 64-bit Word-boxing are present here. For more detailed information, including consideration, see below (although most of the body is written in Japanese). * https://shuujii.github.io/mruby-hash-benchmark ### Memory Usage Lower value is better. | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 344B | 256B | 0.74419x | | 40 | 1,464B | 840B | 0.57377x | | 200 | 8,056B | 3,784B | 0.46971x | | 500 | 17,169B | 9,944B | 0.57949x | ### Performance Higher value is better. #### `mrb_hash_set` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 1.41847M i/s | 1.36004M i/s | 0.95881x | | 40 | 0.39224M i/s | 0.31888M i/s | 0.81296x | | 200 | 0.03780M i/s | 0.04290M i/s | 1.13494x | | 500 | 0.01225M i/s | 0.01314M i/s | 1.07275x | #### `mrb_hash_get` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 26.05920M i/s | 30.19543M i/s | 1.15872x | | 40 | 44.26420M i/s | 32.75781M i/s | 0.74005x | | 200 | 44.55171M i/s | 31.56926M i/s | 0.70860x | | 500 | 39.19250M i/s | 29.73806M i/s | 0.75877x | #### `mrb_hash_each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 25.11964M i/s | 30.34167M i/s | 1.20789x | | 40 | 11.74253M i/s | 13.25539M i/s | 1.12884x | | 200 | 2.01133M i/s | 2.97214M i/s | 1.47770x | | 500 | 0.87411M i/s | 1.21178M i/s | 1.38631x | #### `Hash#[]=` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.50095M i/s | 0.56490M i/s | 1.12764x | | 40 | 0.19132M i/s | 0.18392M i/s | 0.96129x | | 200 | 0.03624M i/s | 0.03256M i/s | 0.89860x | | 500 | 0.01527M i/s | 0.01236M i/s | 0.80935x | #### `Hash#[]` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 11.53211M i/s | 12.78806M i/s | 1.10891x | | 40 | 15.26920M i/s | 13.37529M i/s | 0.87596x | | 200 | 15.28550M i/s | 13.36410M i/s | 0.87430x | | 500 | 14.57695M i/s | 12.75388M i/s | 0.87494x | #### `Hash#each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.30462M i/s | 0.27080M i/s | 0.88898x | | 40 | 0.12912M i/s | 0.11704M i/s | 0.90642x | | 200 | 0.02638M i/s | 0.02402M i/s | 0.91071x | | 500 | 0.01066M i/s | 0.00959M i/s | 0.89953x | #### `Hash#delete` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 7.84167M i/s | 6.96419M i/s | 0.88810x | | 40 | 6.91292M i/s | 7.41427M i/s | 1.07252x | | 200 | 3.75952M i/s | 7.32080M i/s | 1.94727x | | 500 | 2.10754M i/s | 7.05963M i/s | 3.34970x | #### `Hash#shift` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 14.66444M i/s | 13.18876M i/s | 0.89937x | | 40 | 11.95124M i/s | 11.10420M i/s | 0.92913x | | 200 | 5.53681M i/s | 7.88155M i/s | 1.42348x | | 500 | 2.96728M i/s | 5.40405M i/s | 1.82121x | #### `Hash#dup` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.15063M i/s | 5.37889M i/s | 35.71024x | | 40 | 0.06515M i/s | 3.38196M i/s | 51.91279x | | 200 | 0.01359M i/s | 1.46538M i/s | 107.84056x | | 500 | 0.00559M i/s | 0.75411M i/s | 134.88057x | ### Binary Size Lower value is better. | File | Baseline | New | Factor | |:-----------|--------------:|--------------:|----------:| | mruby | 730,408B | 734,176B | 1.00519x | | libmruby.a | 1,068,134B | 1,072,846B | 1.00441x | ## Other Fixes The following issues have also been fixed in the parts where there was some change this time. * [Heap use-after-free in `Hash#value?`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-hash-value-md) * [Heap use-after-free in `ht_hash_equal`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_equal-md) * [Heap use-after-free in `ht_hash_func`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_func-md) * [Heap use-after-free in `mrb_hash_merge`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-mrb_hash_merge-md) * [Self-replacement does not work for `Hash#replace`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-self-replacement-does-not-work-for-hash-replace-md) * [Repeated deletes and inserts increase memory usage of `Hash`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-repeated-deletes-and-inserts-increase-memory-usage-of-hash-md) * [`Hash#rehash` does not reindex completely](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-hash-rehash-does-not-reindex-completely-md) * `mrb_hash_delete_key` does not cause an error for frozen object * `mrb_hash_new_capa` does not allocate required space first * [`mrb_os_memsize_of_hash_table` result is incorrect](https://github.com/mruby/mruby/pull/5032#discussion_r457994075) --- test/t/hash.rb | 1184 ++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 903 insertions(+), 281 deletions(-) (limited to 'test') diff --git a/test/t/hash.rb b/test/t/hash.rb index cd47d251d..c51af03aa 100644 --- a/test/t/hash.rb +++ b/test/t/hash.rb @@ -1,378 +1,1000 @@ ## # Hash ISO Test -assert('Hash', '15.2.13') do - assert_equal Class, Hash.class -end +class HashKey + attr_accessor :value, :error, :callback -assert('Hash#==', '15.2.13.4.1') do - assert_true({ 'abc' => 'abc' } == { 'abc' => 'abc' }) - assert_false({ 'abc' => 'abc' } == { 'cba' => 'cba' }) - assert_false({ :a => 1 } == true) - skip unless Object.const_defined?(:Float) - assert_true({ :equal => 1 } == { :equal => 1.0 }) -end + self.class.alias_method :[], :new -assert('Hash#[]', '15.2.13.4.2') do - a = { 'abc' => 'abc' } + def initialize(value, error: nil, callback: nil) + @value = value + @error = error + @callback = callback + end - assert_equal 'abc', a['abc'] + def ==(other) + @callback.(:==, self, other) if @callback + return raise_error(:==) if @error == true || @error == :== + other.kind_of?(self.class) && @value == other.value + end - # Hash#[] should call #default (#3272) - hash = {} - def hash.default(k); self[k] = 1; end - hash[:foo] += 1 + def eql?(other) + @callback.(:eql?, self, other) if @callback + return raise_error(:eql?) if @error == true || @error == :eql? + other.kind_of?(self.class) && @value.eql?(other.value) + end - assert_equal 2, hash[:foo] -end + def hash + @callback.(:hash, self) if @callback + return raise_error(:hash) if @error == true || @error == :hash + @value % 3 + end -assert('Hash#[]=', '15.2.13.4.3') do - a = Hash.new - a['abc'] = 'abc' + def to_s + "#{self.class}[#{@value}]" + end + alias inspect to_s - assert_equal 'abc', a['abc'] + def raise_error(name) + raise "##{self}: #{name} error" + end end -assert('Hash#clear', '15.2.13.4.4') do - a = { 'abc' => 'abc' } - a.clear - - assert_equal({ }, a) +class HashEntries < Array + self.class.alias_method :[], :new + + def initialize(entries) self.replace(entries) end + def key(index, k=get=true) get ? self[index][0] : (self[index][0] = k) end + def value(index, v=get=true) get ? self[index][1] : (self[index][1] = v) end + def keys; map{|k, v| k} end + def values; map{|k, v| v} end + def each_key(&block) each{|k, v| block.(k)} end + def each_value(&block) each{|k, v| block.(v)} end + def dup2; self.class[*map{|k, v| [k.dup, v.dup]}] end + def to_s; "#{self.class}#{super}" end + alias inspect to_s + + def hash_for(hash={}, &block) + each{|k, v| hash[k] = v} + block.(hash) if block + hash + end end -assert('Hash#dup') do - a = { 'a' => 1 } - b = a.dup - a['a'] = 2 - assert_equal({'a' => 1}, b) - - c = Hash.new { |h, k| h[k] = k.upcase } - d = c.dup - assert_equal("FOO", d["foo"]) +def ar_entries + HashEntries[ + [1, "one"], + [HashKey[2], :two], + [nil, :two], + [:one, 1], + ["&", "&"], + [HashKey[6], :six], + [HashKey[5], :five], # same hash code as HashKey[2] + ] +end + +def ht_entries + ar_entries.dup.push( + ["id", 32], + [:date, "2020-05-02"], + [200, "OK"], + ["modifiers", ["left_shift", "control"]], + [:banana, :yellow], + ["JSON", "JavaScript Object Notation"], + [:size, :large], + ["key_code", "h"], + ["h", 0x04], + [[3, 2, 1], "three, two, one"], + [:auto, true], + [HashKey[12], "December"], + [:path, "/path/to/file"], + [:name, "Ruby"], + ) +end + +def merge_entries!(entries1, entries2) + entries2.each do |k2, v2| + entry1 = entries1.find{|k1, _| k1.eql?(k2)} + entry1 ? (entry1[1] = v2) : (entries1 << [k2, v2]) + end + entries1 +end + +def product(*arrays, &block) + sizes = Array.new(arrays.size+1, 1) + (arrays.size-1).downto(0){|i| sizes[i] = arrays[i].size * sizes[i+1]} + size = sizes[0] + results = Array.new(size){[]} + arrays.each_with_index do |array, arrays_i| + results_i = -1 + (size / sizes[arrays_i]).times do + array.each do |v| + sizes[arrays_i+1].times{results[results_i+=1] << v} + end + end + end + results.each{block.(_1)} end -assert('Hash#default', '15.2.13.4.5') do - a = Hash.new - b = Hash.new('abc') - c = Hash.new {|s,k| s[k] = k} - - assert_nil a.default - assert_equal 'abc', b.default - assert_nil c.default - assert_equal 'abc', c.default('abc') +def assert_iterator(exp, obj, meth) + params = [] + obj.__send__(meth) {|param| params << param} + assert_equal(exp, params) end -assert('Hash#default=', '15.2.13.4.6') do - a = { 'abc' => 'abc' } - a.default = 'cba' - - assert_equal 'abc', a['abc'] - assert_equal 'cba', a['notexist'] +def assert_nothing_crashed(&block) + block.call rescue nil + pass end -assert('Hash#default_proc', '15.2.13.4.7') do - a = Hash.new - b = Hash.new {|s,k| s[k] = k + k} - c = b[2] - d = b['cat'] - - assert_nil a.default_proc - assert_equal Proc, b.default_proc.class - assert_equal 4, c - assert_equal 'catcat', d +assert('Hash', '15.2.13') do + assert_equal(Class, Hash.class) +end + +[[:==, '15.2.13.4.1'], [:eql?, '']].each do |meth, iso| + assert("Hash##{meth}", iso) do + cls = Class.new(Hash){attr_accessor :foo} + [ar_entries, ht_entries].each do |entries| + h1 = entries.hash_for + h2 = entries.dup.reverse!.hash_for + assert_operator(h1, meth, h2) + assert_operator(h1, meth, h1) + assert_not_operator(h1, meth, true) + assert_operator({}, meth, Hash.new) + + h1 = entries.hash_for(cls.new(1)) {|h| h.foo = 1} + h2 = entries.hash_for(cls.new(2)) {|h| h.foo = 2} + assert_operator(h1, meth, h2) + + h1 = entries.hash_for + h2 = entries.hash_for(cls.new) + assert_operator(h1, meth, h2) + + h1 = (entries.dup << [:_k, 1]).hash_for + h2 = (entries.dup << [:_k, 2]).hash_for + assert_not_operator(h1, meth, h2) + + h1 = (entries.dup << [:_k1, 0]).hash_for + h2 = (entries.dup << [:_k2, 0]).hash_for + assert_not_operator(h1, meth, h2) + + h1 = entries.hash_for + h2 = (entries.dup << [:_k, 2]).hash_for + assert_not_operator(h1, meth, h2) + + k1, v1 = HashKey[-1], HashKey[-2] + k2, v2 = HashKey[-1], HashKey[-2] + h1 = (entries.dup << [k1, v1]).hash_for + h2 = (entries.dup << [k2, v2]).hash_for + product([h1, h2], [k1, k2], %i[eql? hash]) do |h, k, m| + [k1, k2].each{_1.callback = nil} + k.callback = ->(name, *){h.clear if name == m} + assert_nothing_crashed{h1.__send__(meth, h2)} + end + product([h1, h2], [v1, v2]) do |h, v| + [v1, v2].each{_1.callback = nil} + v.callback = ->(name, *){h.clear if name == meth} + assert_nothing_crashed{h1.__send__(meth, h2)} + end + + if Object.const_defined?(:Float) + h1 = (entries.dup << [-1, true]).hash_for + h2 = (entries.dup << [-1.0, true]).hash_for + assert_not_operator(h1, meth, h2) + h1 = (entries.dup << [-1.0, true]).hash_for + h2 = (entries.dup << [-1, true]).hash_for + assert_not_operator(h1, meth, h2) + + h1 = (entries.dup << [:_k, 1]).hash_for + h2 = (entries.dup << [:_k, 1.0]).hash_for + if meth == :== + assert_operator(h1, meth, h2) + else + assert_not_operator(h1, meth, h2) + end + end + end + end end -assert('Hash#delete', '15.2.13.4.8') do - a = { 'abc' => 'ABC' } - b = { 'abc' => 'ABC' } - b_tmp_1 = false - b_tmp_2 = false - - assert_equal 'ABC', a.delete('abc') - b.delete('abc') do |k| - b_tmp_1 = true - end - b.delete('abc') do |k| - b_tmp_2 = true +assert('Hash#[]', '15.2.13.4.2') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + assert_equal(entries.size, h.size) + entries.each{|k, v| assert_equal(v, h[k])} + assert_equal(nil, h["_not_found_"]) + assert_equal(nil, h[:_not_dound_]) + assert_equal(nil, h[-2]) + + k = HashKey[-4] + h[HashKey[-1]] = -1 + h[k] = -4 + h.delete(k) + assert_equal(nil, h[k]) + + if Object.const_defined?(:Float) + h[-2] = 22 + assert_equal(nil, h[-2.0]) + h[-3.0] = 33 + assert_equal(nil, h[-3]) + assert_equal(33, h[-3.0]) + end + + k = HashKey[-2] + k.callback = ->(name, *){h.clear if name == :eql?} + assert_nothing_crashed{h[k]} + k.callback = ->(name, *){h.clear if name == :hash} + assert_nothing_crashed{h[k]} end - assert_nil a.delete('cba') - assert_false a.has_key?('abc') - assert_false b_tmp_1 - assert_true b_tmp_2 + # Hash#[] should call #default (#3272) + h = {} + def h.default(k); self[k] = 1; end + h[:foo] += 1 + assert_equal(2, h[:foo]) +end + +[%w[[]= 3], %w[store 26]].each do |meth, no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [{}, ht_entries.hash_for].each do |h| + # duplicated key + k = :_dup_key + h.__send__(meth, k, 1) + size = h.size + h.__send__(meth, k, 2) + assert_equal(size, h.size) + assert_equal(2, h[k]) + + # freeze string key + k = "_mutable" + h.__send__(meth, k, 1) + h_k = h.keys[-1] + assert_not_same(k, h_k) + assert_predicate(h_k, :frozen?) + assert_not_predicate(k, :frozen?) + + # frozen string key + k = "_immutable".freeze + h.__send__(meth, k, 2) + h_k = h.keys[-1] + assert_same(k, h_k) + assert_predicate(h_k, :frozen?) + + # numeric key + if Object.const_defined?(:Float) + h.__send__(meth, 3, :fixnum) + h.__send__(meth, 3.0, :float) + assert_equal(:fixnum, h[3]) + assert_equal(:float, h[3.0]) + h.__send__(meth, 4.0, :float) + h.__send__(meth, 4, :fixnum) + assert_equal(:fixnum, h[4]) + assert_equal(:float, h[4.0]) + end + + # other key + k = [:_array] + h.__send__(meth, k, :_array) + h_k = h.keys[-1] + assert_same(k, h_k) + assert_not_predicate(h_k, :frozen?) + assert_not_predicate(k, :frozen?) + + # deleted key + k1, k2, k3 = HashKey[-1], HashKey[-4], HashKey[-7] # same hash code + h.__send__(meth, k1, 1) + h.__send__(meth, k2, -4) + h.__send__(meth, k3, 73) + size = h.size + h.delete(k1) + h.delete(k2) + h.__send__(meth, k2, 40) + assert_equal(nil, h[k1]) + assert_equal(40, h[k2]) + assert_equal(73, h[k3]) + assert_equal(size - 1, h.size) + + # frozen + h.freeze + assert_raise(FrozenError){h.__send__(meth, -100, 1)} + end + + [ar_entries.hash_for, ht_entries.hash_for].each do |h| + k = HashKey[-2] + k.callback = ->(name, *){h.clear if name == :eql?} + assert_nothing_crashed{h.__send__(meth, k, 2)} + k.callback = ->(name, *){h.clear if name == :hash} + assert_nothing_crashed{h.__send__(meth, k, 2)} + end + end end -assert('Hash#each', '15.2.13.4.9') do - a = { 'abc_key' => 'abc_value' } - key = nil - value = nil - - a.each do |k,v| - key = k - value = v +assert('Hash#clear', '15.2.13.4.4') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + assert_same(h, h.clear) + assert_equal(0, h.size) + assert_nil(h[entries.key(3)]) + + h.freeze + assert_raise(FrozenError){h.clear} end - assert_equal 'abc_key', key - assert_equal 'abc_value', value + h = {}.freeze + assert_raise(FrozenError){h.clear} end -assert('Hash#each_key', '15.2.13.4.10') do - a = { 'abc_key' => 'abc_value' } - key = nil - - a.each_key do |k| - key = k +assert('Hash#dup') do + cls = Class.new(Hash){attr_accessor :foo} + [ar_entries, ht_entries].each do |entries| + h1 = entries.hash_for(cls.new(61)){|h| h.foo = 23}.freeze + h2 = h1.dup + assert_not_predicate(h2, :frozen?) + assert_equal(h1.class, h2.class) + assert_equal(entries, h2.to_a) + assert_equal(23, h2.foo) + assert_equal(61, h2["_not_found_"]) + h2[-10] = 10 + assert_equal(10, h2[-10]) + assert_not_operator(h1, :key?, -10) + + h = entries.hash_for + k = HashKey[-1] + h[k] = 1 + k.callback = ->(*){h.clear} + assert_nothing_crashed{h.dup} end - - assert_equal 'abc_key', key end -assert('Hash#each_value', '15.2.13.4.11') do - a = { 'abc_key' => 'abc_value' } - value = nil - - a.each_value do |v| - value = v +assert('Hash#default', '15.2.13.4.5') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for(Hash.new) + assert_equal(nil, h.default) + assert_equal(nil, h.default(-2)) + + h = entries.hash_for(Hash.new(-88)) + assert_equal(-88, h.default) + assert_equal(-88, h.default(-2)) + assert_not_operator(h, :key?, -2) + assert_raise(ArgumentError){h.default(-2,-2)} + + proc = ->(h, k){h[k] = k * 3} + h = entries.hash_for(Hash.new(proc)) + assert_equal(proc, h.default(-2)) + + h = entries.hash_for(Hash.new(&proc)) + assert_equal(nil, h.default) + assert_not_operator(h, :key?, -2) + assert_equal(-6, h.default(-2)) + assert_equal(-6, h[-2]) + h[-2] = -5 + assert_equal(-6, h.default(-2)) + assert_equal(-6, h[-2]) end - - assert_equal 'abc_value', value end -assert('Hash#empty?', '15.2.13.4.12') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new - - assert_false a.empty? - assert_true b.empty? -end +assert('Hash#default=', '15.2.13.4.6') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for(Hash.new) + h.default = 3 + assert_equal(3, h[-2]) + assert_equal(entries.value(0), h[entries.key(0)]) -assert('Hash#has_key?', '15.2.13.4.13') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new + h.default = 4 + assert_equal(4, h[-2]) - assert_true a.has_key?('abc_key') - assert_false b.has_key?('cba') -end + h.default = nil + assert_equal(nil, h[-2]) -assert('Hash#has_value?', '15.2.13.4.14') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new + h.default = [5] + assert_same(h[-2], h[-3]) - assert_true a.has_value?('abc_value') - assert_false b.has_value?('cba') + h.freeze + assert_raise(FrozenError){h.default = 3} + end end -assert('Hash#include?', '15.2.13.4.15') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new - - assert_true a.include?('abc_key') - assert_false b.include?('cba') +assert('Hash#default_proc', '15.2.13.4.7') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for({}) + assert_nil(h.default_proc) + + h = entries.hash_for(Hash.new(34)) + assert_nil(h.default_proc) + + h = entries.hash_for(Hash.new{|h, k| h[k] = k * 3}) + proc = h.default_proc + assert_equal(Proc, proc.class) + assert_equal(6, proc.(h, 2)) + assert_equal([2, 6], h.to_a[-1]) + end end -assert('Hash#initialize', '15.2.13.4.16') do - # Testing initialize by new. - h = Hash.new - h2 = Hash.new(:not_found) - - assert_true h.is_a? Hash - assert_equal({ }, h) - assert_nil h["hello"] - assert_equal :not_found, h2["hello"] -end +assert('Hash#delete', '15.2.13.4.8') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + pairs = entries.dup + [0, 2, -1].each do |i| + k, v = pairs.delete_at(i) + assert_equal(v, h.delete(k)) + assert_equal(nil, h[k]) + assert_equal(false, h.key?(k)) + end + [entries.key(0), "_not_found_"].each {|k|assert_equal(nil, h.delete(k))} + assert_equal(pairs.size, h.size) + assert_equal(pairs, h.to_a) + pairs.each {|k, v| assert_equal(v, h[k])} + + h = entries.hash_for + pairs = entries.dup + [pairs.delete_at(1), ["_not_found_", "_default"]].each do |k, v| + assert_equal(v, h.delete(k){"_default"}) + assert_equal(nil, h[k]) + assert_equal(false, h.key?(k)) + end + assert_equal(pairs.size, h.size) + assert_equal(pairs, h.to_a) + pairs.each {|k, v| assert_equal(v, h[k])} + + if Object.const_defined?(:Float) + h = entries.dup.push([-5, 1], [-5.0, 2], [-6.0, 3], [-6, 4]).hash_for + assert_equal(1, h.delete(-5)) + assert_equal(3, h.delete(-6.0)) + end + + # nil value with block + h = entries.hash_for + k = "_nil" + h[k] = nil + assert_equal(nil, h.delete(k){"blk"}) + assert_equal(false, h.key?(k)) + + k = HashKey[-31, callback: ->(*){h.clear}] + assert_nothing_crashed{h.delete(k)} + end -assert('Hash#initialize_copy', '15.2.13.4.17') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new.initialize_copy(a) + assert_raise(ArgumentError){{}.delete} + assert_raise(ArgumentError){{}.delete(1,2)} - assert_equal({ 'abc_key' => 'abc_value' }, b) + h = {}.freeze + assert_raise(FrozenError){h.delete(1)} +end + +[%w[each 9], %w[each_key 10], %w[each_value 11]].each do |meth, no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [ar_entries, ht_entries].each do |entries| + exp = [] + entries.__send__(meth){|param| exp << param} + assert_iterator(exp, entries.hash_for, meth) + + h = entries.hash_for + entries.shift + h.shift + entry = entries.delete_at(1) + h.delete(entry[0]) + h.delete(entries.delete_at(-4)[0]) + entries << entry + h.store(*entry) + exp = [] + entries.__send__(meth){|param| exp << param} + assert_iterator(exp, h, meth) + end + + assert_iterator([], {}, meth) + end end -assert('Hash#key?', '15.2.13.4.18') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new +assert('Hash#empty?', '15.2.13.4.12') do + [ar_entries, ht_entries].each do |entries| + assert_not_predicate entries.hash_for, :empty? - assert_true a.key?('abc_key') - assert_false b.key?('cba') -end + h = entries.hash_for + h.shift + h.delete(entries.key(-1)) + assert_not_predicate h, :empty? -assert('Hash#keys', '15.2.13.4.19') do - a = { 'abc_key' => 'abc_value' } + h = entries.hash_for + entries.size.times{h.shift} + assert_predicate(h, :empty?) - assert_equal ['abc_key'], a.keys -end - -assert('Hash#length', '15.2.13.4.20') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new + h = entries.hash_for + entries.each {|k, v| h.delete(k)} + assert_predicate(h, :empty?) + end - assert_equal 1, a.length - assert_equal 0, b.length + assert_predicate(Hash.new, :empty?) + assert_predicate(Hash.new(1), :empty?) + assert_predicate(Hash.new{|h, k| h[k] = 2}, :empty?) end -assert('Hash#member?', '15.2.13.4.21') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new - - assert_true a.member?('abc_key') - assert_false b.member?('cba') -end +[%w[has_key? 13], %w[include? 15], %w[key? 18], %w[member? 21]].each do |meth,no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [ar_entries, ht_entries].each do |entries| + pairs = entries.dup.push([HashKey[-3], 3], [nil, "NIL"]) + h = pairs.hash_for + pairs.each{|k, v| assert_operator(h, meth, k)} + assert_not_operator(h, meth, HashKey[-6]) + assert_not_operator(h, meth, 3) -assert('Hash#merge', '15.2.13.4.22') do - a = { 'abc_key' => 'abc_value', 'cba_key' => 'cba_value' } - b = { 'cba_key' => 'XXX', 'xyz_key' => 'xyz_value' } + if Object.const_defined?(:Float) + hh = entries.push([-7, :i], [-8.0, :f]).hash_for + assert_not_operator(hh, meth, -7.0) + assert_not_operator(hh, meth, -8) + assert_operator(hh, meth, -8.0) + end - result_1 = a.merge b - result_2 = a.merge(b) do |key, original, new| - original - end + h.shift + assert_not_operator(h, meth, pairs.key(0)) - assert_equal({'abc_key' => 'abc_value', 'cba_key' => 'XXX', - 'xyz_key' => 'xyz_value' }, result_1) - assert_equal({'abc_key' => 'abc_value', 'cba_key' => 'cba_value', - 'xyz_key' => 'xyz_value' }, result_2) + h.delete(pairs.key(3)) + assert_not_operator(h, meth, pairs.key(3)) - assert_raise(TypeError) do - { 'abc_key' => 'abc_value' }.merge "a" + k = HashKey[-31, callback: ->(*){h.clear}] + assert_nothing_crashed{h.__send__(meth, k)} + end end -end -assert('Hash#replace', '15.2.13.4.23') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new.replace(a) + h = Hash.new{|h, k| h[1] = 1} + assert_not_operator(h, meth, 1) +end - assert_equal({ 'abc_key' => 'abc_value' }, b) +[%w[has_value? 14], %w[value? 24]].each do |meth, no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [ar_entries, ht_entries].each do |entries| + entries.push([HashKey[-5], -8], ["NIL", nil]) + h = entries.hash_for + entries.each{|k, v| assert_operator(h, meth, v)} + assert_operator(h, meth, -8.0) if Object.const_defined?(:Float) + assert_not_operator(h, meth, "-8") - a = Hash.new(42) - b = {} - b.replace(a) - assert_equal(42, b[1]) + h.shift + assert_not_operator(h, meth, entries.value(0)) - a = Hash.new{|h,x| x} - b.replace(a) - assert_equal(127, b[127]) + h.delete(entries.key(3)) + assert_not_operator(h, meth, entries.value(3)) - assert_raise(TypeError) do - { 'abc_key' => 'abc_value' }.replace "a" + v = HashKey[-31, callback: ->(*){h.clear}] + assert_nothing_crashed{h.__send__(meth, v)} + end end -end - -assert('Hash#shift', '15.2.13.4.24') do - a = { 'abc_key' => 'abc_value', 'cba_key' => 'cba_value' } - b = a.shift - - assert_equal Array, b.class - assert_equal 2, b.size - assert_equal 1, a.size - b = a.shift - - assert_equal Array, b.class - assert_equal 2, b.size - assert_equal 0, a.size + h = Hash.new{|h, k| h[1] = 1} + assert_not_operator(h, meth, 1) end -assert('Hash#size', '15.2.13.4.25') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new - - assert_equal 1, a.size - assert_equal 0, b.size +assert('Hash#initialize', '15.2.13.4.16') do + h = Hash.new + assert_equal(Hash, h.class) + assert_not_operator(h, :key?, 1) + assert_equal(nil, h[1]) + + h = Hash.new([8]) + assert_not_operator(h, :key?, 1) + assert_equal([8], h[1]) + assert_same(h[1], h[2]) + + k = "key" + h = Hash.new{|hash, key| [hash, key]} + assert_not_operator(h, :key?, k) + assert_equal([h, k], h[k]) + assert_same(h, h[k][0]) + assert_same(k, h[k][1]) + + assert_raise(ArgumentError){Hash.new(1,2)} + assert_raise(ArgumentError){Hash.new(1){}} +end + +[%w[keys 19], %w[values 28]].each do |meth, no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + assert_equal(entries.__send__(meth), h.__send__(meth)) + + h.shift + entries.shift + h.delete(entries.delete_at(3)[0]) + assert_equal(entries.__send__(meth), h.__send__(meth)) + end + + assert_equal([], {}.__send__(meth)) + end end -assert('Hash#store', '15.2.13.4.26') do - a = Hash.new - a.store('abc', 'abc') +[%w[length 20], %w[size 25]].each do |meth, no| + assert("Hash##{meth}", "15.2.13.4.#{no}") do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + assert_equal(entries.size, h.__send__(meth)) + + h.shift + entries.shift + h.delete(entries.delete_at(3)[0]) + assert_equal(entries.size, h.__send__(meth)) + end - assert_equal 'abc', a['abc'] + assert_equal(0, Hash.new.__send__(meth)) + end end -assert('Hash#value?', '15.2.13.4.27') do - a = { 'abc_key' => 'abc_value' } - b = Hash.new +assert('Hash#merge', '15.2.13.4.22') do + cls = Class.new(Hash){attr_accessor :foo} + ar_pairs = HashEntries[ + ["id", 32], + [nil, :two], + ["&", "&"], + [:same_key, :AR], + [HashKey[2], 20], + ] + ht_pairs = HashEntries[ + *(1..20).map{[_1, _1.to_s]}, + [:same_key, :HT], + [:age, 32], + [HashKey[5], 500], + ] + + [[ar_pairs, ht_pairs], [ht_pairs, ar_pairs]].each do |entries1, entries2| + h1 = entries1.hash_for(cls.new(:dv1)){|h| h.foo = :iv1}.freeze + h2 = entries2.hash_for(Hash.new(:dv2)).freeze + h3 = h1.merge(h2) + assert_equal(entries1, h1.to_a) + assert_equal(merge_entries!(entries1.dup2, entries2), h3.to_a) + assert_equal(cls, h3.class) + assert_equal(:dv1, h3.default) + assert_equal(:iv1, h3.foo) + + h3 = {}.merge(entries2.hash_for(cls.new)) + assert_equal(merge_entries!([], entries2), h3.to_a) + assert_equal(Hash, h3.class) + + h3 = entries1.hash_for.merge({}) + assert_equal(merge_entries!(entries1.dup2, []), h3.to_a) + + h1 = entries1.hash_for + h2 = entries2.hash_for + h3 = h1.merge(h2){|k, v1, v2| [k, v1, v2]} + exp = merge_entries!(entries1.dup2, entries2) + exp.find{|k, _| k == :same_key}[1] = [ + :same_key, + entries1.find{|k, _| k == :same_key}[1], + entries2.find{|k, _| k == :same_key}[1], + ] + assert_equal(exp, h3.to_a) + + assert_raise(TypeError){entries1.hash_for.merge("str")} + + k2 = HashKey[-2] + entries2 << [k2, 234] + h1, h2 = entries1.hash_for, entries2.hash_for + k2.callback = ->(name, *){h1.clear if name == :eql?} + assert_nothing_crashed{h1.merge(h2)} + h1, h2 = entries1.hash_for, entries2.hash_for + k2.callback = ->(name, *){h2.clear if name == :eql?} + assert_nothing_crashed{h1.merge(h2)} + h1, h2 = entries1.hash_for, entries2.hash_for + k2.callback = ->(name, *){h1.clear if name == :hash} + assert_nothing_crashed{h1.merge(h2)} + h1, h2 = entries1.hash_for, entries2.hash_for + k2.callback = ->(name, *){h2.clear if name == :hash} + assert_nothing_crashed{h1.merge(h2)} + end +end - assert_true a.value?('abc_value') - assert_false b.value?('cba') +assert("Hash#replace", "15.2.13.4.23") do + cls = Class.new(Hash){attr_accessor :foo} + e = [ar_entries, ht_entries] + [e, e.reverse].each do |entries1, entries2| + h1 = entries1.hash_for + assert_same(h1, h1.replace(h1)) + assert_equal(entries1, h1.to_a) + + h1 = {} + assert_same(h1, h1.replace(entries2.hash_for)) + assert_equal(entries2, h1.to_a) + + h1 = entries1.hash_for + assert_same(h1, h1.replace({})) + assert_predicate(h1, :empty?) + + pairs2 = entries2.dup + h2 = pairs2.hash_for + pairs2.shift + h2.shift + h2.delete(pairs2.delete_at(2)[0]) + h2.delete(pairs2.delete_at(4)[0]) + h1 = entries1.hash_for + assert_same(h1, h1.replace(h2)) + assert_equal(pairs2, h1.to_a) + + h1 = entries1.hash_for(Hash.new(10)) + h2 = entries2.hash_for(Hash.new(20)) + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + assert_equal(20, h1.default) + + h1 = entries1.hash_for(Hash.new{_2}) + h2 = entries2.hash_for(Hash.new{_2.to_s}) + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + assert_equal("-11", h1[-11]) + + h1 = entries1.hash_for(Hash.new(10)) + h2 = entries2.hash_for(Hash.new{_2.to_s}) + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + assert_equal("-11", h1[-11]) + + h1 = entries1.hash_for(Hash.new{_2}) + h2 = entries2.hash_for(Hash.new(20)) + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + assert_equal(20, h1[-1]) + + h1 = entries1.hash_for(cls.new(10)){|h| h.foo = 41} + h2 = entries2.hash_for(cls.new(20)){|h| h.foo = 42}.freeze + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + assert_equal(20, h1.default) + assert_equal(41, h1.foo) + + h1 = entries1.hash_for + h2 = entries2.hash_for(cls.new) + assert_same(h1, h1.replace(h2)) + assert_equal(entries2, h1.to_a) + + assert_raise(TypeError){entries1.hash_for.replace([])} + + k2 = HashKey[-2] + pairs2 = entries2.dup + pairs2 << [k2, 23] + h1 = entries1.hash_for + h2 = pairs2.hash_for + k2.callback = ->(*){h1.clear; h2.clear} + assert_nothing_crashed{h1.replace(h2)} + + assert_raise(FrozenError){h1.freeze.replace(h1)} + assert_raise(FrozenError){{}.freeze.replace({})} + end end -assert('Hash#values', '15.2.13.4.28') do - a = { 'abc_key' => 'abc_value' } +assert('Hash#shift', '15.2.13.4.24') do + [ar_entries, ht_entries].each do |entries| + pairs = entries.dup + h = pairs.hash_for + h.delete(pairs.delete_at(0)[0]) + h.delete(pairs.delete_at(3)[0]) + until pairs.empty? + exp = pairs.shift + act = h.shift + assert_equal(Array, act.class) + assert_equal(exp, act) + assert_equal(exp.size, act.size) + assert_not_operator(h, :key?, exp[0]) + end + + assert_equal(nil, h.shift) + assert_equal(0, h.size) + + h.default = -456 + assert_equal(-456, h.shift) + assert_equal(0, h.size) + + h.freeze + assert_raise(FrozenError){h.shift} + end - assert_equal ['abc_value'], a.values + h = Hash.new{|h, k| [h, k]} + assert_operator(h.shift, :eql?, [h, nil]) + assert_equal(0, h.size) end # Not ISO specified -assert('Hash#eql?') do - a = { 'a' => 1, 'b' => 2, 'c' => 3 } - b = { 'a' => 1, 'b' => 2, 'c' => 3 } - c = { 'a' => 1.0, 'b' => 2, 'c' => 3 } - assert_true(a.eql?(b)) - assert_false(a.eql?(c)) - assert_false(a.eql?(true)) -end - -assert('Hash#reject') do - h = {:one => 1, :two => 2, :three => 3, :four => 4} - ret = h.reject do |k,v| - v % 2 == 0 +%i[reject select].each do |meth| + assert("Hash##{meth}") do + cls = Class.new(Hash){attr_accessor :foo} + [ar_entries, ht_entries].each do |entries| + params = nil + filter = ->((k, v)) do + params << [k, v] + String === k + end + + h = entries.hash_for(cls.new(1)) + params = [] + ret = h.__send__(meth, &filter) + assert_equal(entries, params) + assert_equal(entries, h.to_a) + assert_equal(1, h.default) + assert_equal(entries.__send__(meth, &filter), ret.to_a) + assert_equal(Hash, ret.class) + assert_equal(nil, ret.default) + + params = [] + assert_predicate({}.__send__(meth, &filter), :empty?) + assert_predicate(params, :empty?) + end end - assert_equal({:one => 1, :three => 3}, ret) - assert_equal({:one => 1, :two => 2, :three => 3, :four => 4}, h) end -assert('Hash#reject!') do - h = {:one => 1, :two => 2, :three => 3, :four => 4} - ret = h.reject! do |k,v| - v % 2 == 0 +%i[reject! select!].each do |meth| + assert("Hash##{meth}") do + [ar_entries, ht_entries].each do |entries| + params = nil + filter = ->((k, v)) do + params << [k, v] + String === k + end + + pairs = entries.dup << ["_str", 5] + h = pairs.hash_for(Hash.new(1)) + params = [] + ret = h.__send__(meth, &filter) + assert_same(h, ret) + assert_equal(pairs, params) + assert_equal(pairs.__send__(meth.to_s[0..-2], &filter), h.to_a) + assert_equal(1, h.default) + + h = pairs.hash_for + ret = h.__send__(meth){meth == :select!} + assert_nil(ret) + assert_equal(pairs, h.to_a) + + assert_raise(FrozenError){h.freeze.__send__(meth, &filter)} + end + + h = {} + assert_nil(h.__send__(meth){}) + assert_predicate(h, :empty?) end - assert_equal({:one => 1, :three => 3}, ret) - assert_equal({:one => 1, :three => 3}, h) end -assert('Hash#select') do - h = {:one => 1, :two => 2, :three => 3, :four => 4} - ret = h.select do |k,v| - v % 2 == 0 +%i[inspect to_s].each do |meth| + assert("Hash##{meth}") do + assert_equal('{}', Hash.new.__send__(meth)) + + h1 = {:s => 0, :a => [1,2], 37 => :b, :d => "del", "c" => nil} + h1.shift + h1.delete(:d) + s1 = ':a=>[1, 2], 37=>:b, "c"=>nil' + h2 = Hash.new(100) + + (1..14).each{h2[_1] = _1 * 2} + h2 = {**h2, **h1} + s2 = "1=>2, 2=>4, 3=>6, 4=>8, 5=>10, 6=>12, 7=>14, 8=>16, " \ + "9=>18, 10=>20, 11=>22, 12=>24, 13=>26, 14=>28, #{s1}" + + [[h1, s1], [h2, s2]].each do |h, s| + assert_equal("{#{s}}", h.__send__(meth)) + + hh = {} + hh[:recur] = hh + h.each{|k, v| hh[k] = v} + assert_equal("{:recur=>{...}, #{s}}", hh.__send__(meth)) + + hh = h.dup + hh[hh] = :recur + assert_equal("{#{s}, {...}=>:recur}", hh.__send__(meth)) + end + + [ar_entries, ht_entries].each do |entries| + cls = Class.new do + attr_accessor :h + def inspect; @h.replace(@h.dup); to_s; end + end + v = cls.new + h = entries.hash_for({_k: v}) + v.h = h + assert_nothing_raised{h.__send__(meth)} + end end - assert_equal({:two => 2, :four => 4}, ret) - assert_equal({:one => 1, :two => 2, :three => 3, :four => 4}, h) end -assert('Hash#select!') do - h = {:one => 1, :two => 2, :three => 3, :four => 4} - ret = h.select! do |k,v| - v % 2 == 0 +assert('Hash#rehash') do + cls = Class.new(Hash){attr_accessor :foo} + [ar_entries, ht_entries].each do |entries| + k1, k2, k3 = HashKey[-1], HashKey[-2], HashKey[-3] + pairs = entries.dup.push( + [-4, -40], + [HashKey[-11], -5], + [:_del, "_del"], + [k1, :_k1], + ["_a", "_b"], + [k2, :_k2], + ["_c", "_d"], + [HashKey[-22], -21], + [k3, :_k3], + ) + h = pairs.hash_for(cls.new(:defvar)){|h| h.foo = "f"} + k1.value, k2.value, k3.value = -11, -11, -22 + pairs1 = pairs.dup + pairs1.delete([:_del, h.delete(:_del)]) + exp_pairs1 = pairs1.hash_for.to_a + h.freeze + assert_same(h, h.rehash) + assert_equal(exp_pairs1, h.to_a) + assert_equal(exp_pairs1.size, h.size) + assert_equal(:defvar, h.default) + assert_equal("f", h.foo) + exp_pairs1.each {|k, v| assert_equal(v, h[k])} + + # If an error occurs during rehash, at least the entry list is not broken. + k1.value, k2.value, k3.value = -1, -2, -3 + h = pairs.hash_for + k1.value = -11 + pairs2 = pairs.dup + pairs2.delete([:_del, h.delete(:_del)]) + exp_pairs2 = pairs2.hash_for.to_a + k2.error = :eql? + assert_raise{h.rehash} + act_pairs2 = h.to_a + unless pairs2 == act_pairs2 && pairs2.size == h.size + assert_equal(exp_pairs2, act_pairs2) + assert_equal(exp_pairs2.size, h.size) + end + + k1.value = -1 + k2.error = false + h = pairs.hash_for + k1.callback = ->(name, *){h.clear if name == :eql?} + assert_nothing_crashed{h.rehash} + k1.callback = ->(name, *){h.clear if name == :hash} + assert_nothing_crashed{h.rehash} end - assert_equal({:two => 2, :four => 4}, ret) - assert_equal({:two => 2, :four => 4}, h) -end - -# Not ISO specified - -assert('Hash#inspect') do - h = { "c" => 300, "a" => 100, "d" => 400, "c" => 300 } - h["recur"] = h - ret = h.to_s - assert_include ret, '"c"=>300' - assert_include ret, '"a"=>100' - assert_include ret, '"d"=>400' - assert_include ret, '"recur"=>{...}' + h = {} + assert_same(h, h.rehash) + assert_predicate(h, :empty?) +end + +assert('#eql? receiver should be specified key') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + k0 = HashKey[-99] + h[k0] = 1 + + k1 = HashKey[-3, error: :eql?] + assert_raise{h[k1]} + k0.error = :eql? + k1.error = false + assert_nothing_raised{h[k1]} + + k0.error = false + k1.error = :eql? + assert_raise{h[k1] = 1} + k0.error = :eql? + k1.error = false + assert_nothing_raised{h[k1] = 1} + + k0.error = false + k2 = HashKey[-6, error: :eql?] + assert_raise{h.delete(k2)} + k0.error = :eql? + k2.error = false + assert_nothing_raised{h.delete(k2)} + + k0.error = false + k3 = HashKey[-9, error: :eql?] + %i[has_key? include? key? member?].each do |m| + assert_raise{h.__send__(m, k3)} + end + k0.error = :eql? + k3.error = false + %i[has_key? include? key? member?].each do |m| + assert_nothing_raised{h.__send__(m, k3)} + end + end end -assert('Hash#rehash') do - h = {[:a] => "b"} - # hash key modified - h.keys[0][0] = :b - # h[[:b]] => nil - h.rehash - assert_equal("b", h[[:b]]) -end +assert('#== receiver should be specified value') do + [ar_entries, ht_entries].each do |entries| + h = entries.hash_for + v0 = HashKey[-99] + h[-99] = v0 -assert('Hash#freeze') do - h = {}.freeze - assert_raise(FrozenError) do - h[:a] = 'b' + v1 = HashKey[-3, error: :==] + %i[has_value? value?].each{|m| assert_raise{h.__send__(m, v1)}} + v0.error = :== + v1.error = false + %i[has_value? value?].each{|m| assert_nothing_raised{h.__send__(m, v1)}} end end -- cgit v1.2.3