[Bug #21170]

st_table reserves -1 as a special hash value to indicate that an entry
has been deleted. So that that's a valid value to be returned from the
hash function, do_hash replaces -1 with 0 so that it is not mistaken for
the sentinel.

Previously, when upgrading an AR table to an ST table,
rb_st_add_direct_with_hash was used which did not perform the same
conversion, this could lead to a hash in a broken state where one if its
entries which was supposed to exist being marked as a tombstone.

The hash could then become further corrupted when the ST table required
resizing as the falsely tombstoned entry would be skipped but it would
be counted in num entries, leading to an uninitialized entry at index
15.

In most cases this will be really rare, unless using a very poorly
implemented custom hash function.

This also adds two debug assertions, one that st_add_direct_with_hash
does not receive the reserved hash value, and a second in
rebuild_table_with, which ensures that after we rebuild/compact a table
it contains the expected number of elements.

Co-authored-by: Alan Wu <alanwu@ruby-lang.org>

	[Bug #20307] Fix `Hash#update` to make frozen copy of string keys

Merged into master in 7ba2506232d3fa6c4e82e3708c0ff746a1a8de5c

[Bug #20050]

	[Bug #19969] Compact st_table after deleted if possible

	---
	 hash.c                 | 19 +++++++++++++++++++
	 st.c                   | 40 +++++++++++++++++++++++++++++-----------
	 test/ruby/test_hash.rb |  9 +++++++++
	 3 files changed, 57 insertions(+), 11 deletions(-)

	hash.c: Fix hash_iter_lev_dec corrupting shape

	[Bug #19589]

	When decrementing `iter_lev` from `65` to `64` the flags would be
	corrupted, causing the shape_id to be invalid.
	---
	 hash.c                 | 12 +++++++++---
	 test/ruby/test_hash.rb | 11 +++++++++++
	 2 files changed, 20 insertions(+), 3 deletions(-)

opt_aref_with is an optimized instruction for accessing a Hash using a
non-frozen string key (ie. from a file without frozen_string_literal).
It attempts to avoid allocating the string, and instead silently using a
frozen string (hash string keys are always fstrings).

Because this is just an optimization, it should be invisible to the
user. However, previously this optimization was could be seen via hashes
with default procs.

For example, previously:

    h = Hash.new { |h, k| k.frozen? }
    str = "foo"
    h[str]   # false
    h["foo"] # true when optimizations enabled

This commit checks that the Hash doesn't have a default proc when using
opt_aref_with.

Previously, because opt_aref and opt_aset don't push a frame, when they
would call rb_hash to determine the hash value of the key, the initial
level of recursion would incorrectly use the method id at the top of the
stack instead of "hash".

This commit replaces rb_exec_recursive_outer with
rb_exec_recursive_outer_mid, which takes an explicit method id, so that
we can make the hash calculation behave consistently.

rb_exec_recursive_outer was documented as being internal, so I believe
this should be okay to change.

tab->entries_bound is used to check if the bins are full in
rebuild_table_if_necessary.

Hash#shift against an empty hash assigned 0 to tab->entries_bound, but
didn't clear the bins. Thus, the table is not rebuilt even when the bins
are full. Attempting to add a new element into full-bin hash gets stuck.

This change stops clearing tab->entries_bound in Hash#shift.
[Bug #18578]

Fixes [Bug #16908]

[Feature #14579]