Project

General

Profile

Actions

Bug #17488

closed

Regression in Ruby 3: Hash#key? is non-deterministic when argument uses DelegateClass

Added by myronmarston (Myron Marston) over 1 year ago. Updated over 1 year ago.

Status:
Closed
Priority:
Normal
Assignee:
-
Target version:
-
ruby -v:
ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-darwin19]
[ruby-core:101794]

Description

Upon upgrading a library to run on Ruby 3.0, I have observed that Hash#key? has non-deterministic behavior when the argument uses DelegateClass. This non-deterministic behavior was not present in Ruby 2.7.

Reproducing this is slightly difficult; the behavior appears to be deterministic (but not necessarily correct) within a single ruby process. To reproduce the non-determinism, you need to start ruby many times to observe different results. My script below does this.

Reproduction script

puts "Running on Ruby: #{RUBY_DESCRIPTION}"

program = <<~EOS
  require "delegate"
  TypeName = DelegateClass(String)

  hash = {
    "Int" => true,
    "Float" => true,
    "String" => true,
    "Boolean" => true,
    "WidgetFilter" => true,
    "WidgetAggregation" => true,
    "WidgetEdge" => true,
    "WidgetSortOrder" => true,
    "WidgetGrouping" => true,
  }

  puts hash.key?(TypeName.new("WidgetAggregation"))
EOS

iterations = 20
results = iterations.times.map { `ruby -e '#{program}'`.chomp }.tally

puts "Results of checking `Hash#key?` #{iterations} times: #{results.inspect}"

Put this in a file like ruby3_hash_bug.rb, and run it using either Ruby 2.7 (to see Hash#key? consistently return true) or Ruby 3.0 (to see Hash#key? produce non-deterministic behavior).

Ruby 2.7 results

Running on Ruby: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x86_64-darwin19]
Results of checking `Hash#key?` 20 times: {"true"=>20}

Ruby 3.0 results

Running on Ruby: ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-darwin19]
Results of checking `Hash#key?` 20 times: {"true"=>12, "false"=>8}

Note that the ratio of true to false is non-deterministic; here are a couple other runs on Ruby 3.0 with different results:

Running on Ruby: ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-darwin19]
Results of checking `Hash#key?` 20 times: {"false"=>7, "true"=>13}
Running on Ruby: ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-darwin19]
Results of checking `Hash#key?` 20 times: {"true"=>11, "false"=>9}

Updated by marcandre (Marc-Andre Lafortune) over 1 year ago

I didn't run a git bisect, but this was the case already in ruby 3.0.0preview1

Updated by marcandre (Marc-Andre Lafortune) over 1 year ago

Bug requires more than 8 keys (as in the example)

Updated by shyouhei (Shyouhei Urabe) over 1 year ago

  • Status changed from Open to Feedback

Hello, I cannot reproduce this on any of ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-linux] compiled using {clang-{3,4,5,6,7,8,9,10,11,12),gcc-{4,5,6,7,8,9,10}} on my Linux box. Maybe an XCode glitch I suspect?

I have just restored the ruby.h branch. @nobu (Nobuyoshi Nakada) can you bisect on this branch as well to spot the actual change? Sorry for the trouble. It was my bad to press the squash button when I merged this.

https://github.com/shyouhei/ruby/tree/ruby.h

Also I want to know your clang --version.

Updated by marcandre (Marc-Andre Lafortune) over 1 year ago

shyouhei (Shyouhei Urabe) wrote in #note-4:

Also I want to know your clang --version.

$ clang --version
Apple clang version 11.0.0 (clang-1100.0.33.17)
Target: x86_64-apple-darwin18.7.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

Updated by marcandre (Marc-Andre Lafortune) over 1 year ago

On my mac pro (High Sierra) too:

$ clang --version
Apple LLVM version 10.0.0 (clang-1000.11.45.2)
Target: x86_64-apple-darwin17.7.0
Thread model: posix
InstalledDir: /Volumes/Media/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

Updated by sekiyama (Tomoki Sekiyama) over 1 year ago

I have confirmed this too in ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-linux] built with gcc (Debian 8.3.0-6) 8.3.0.

And also confirmed that this PR fixes the issue:
https://github.com/ruby/ruby/pull/4014

Actions #8

Updated by nobu (Nobuyoshi Nakada) over 1 year ago

  • Status changed from Feedback to Closed

Applied in changeset git|20a8425aa0f9a947e72b06cbd3a2afe9674dd18f.


Make any hash values fixable [Bug #17488]

As hnum is an unsigned st_index_t, the result of RSHIFT may not be
in the fixable range.

Co-authored-by: NeoCat

Updated by nobu (Nobuyoshi Nakada) over 1 year ago

shyouhei (Shyouhei Urabe) wrote in #note-4:

Hello, I cannot reproduce this on any of ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-linux] compiled using {clang-{3,4,5,6,7,8,9,10,11,12),gcc-{4,5,6,7,8,9,10}} on my Linux box. Maybe an XCode glitch I suspect?

I could confirm that test_any_hash_fixable fails on the followings.

gcc (Ubuntu 10.2.0-13ubuntu1) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Apple clang version 11.0.3 (clang-1103.0.32.62)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
gcc-mp-10 (MacPorts gcc10 10.2.0_4) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I have just restored the ruby.h branch. @nobu (Nobuyoshi Nakada) can you bisect on this branch as well to spot the actual change? Sorry for the trouble. It was my bad to press the squash button when I merged this.

https://github.com/shyouhei/ruby/tree/ruby.h

03670392f46f00a4f92c41a3c7ea6215138037a6 is the first bad commit
commit 03670392f46f00a4f92c41a3c7ea6215138037a6
Author: 卜部昌平 <shyouhei@ruby-lang.org>
Date:   Mon Mar 9 11:58:34 2020 +0900

    include/ruby/3/arithmetic/long.h rework
    
    Turned macros into inline functions.

 include/ruby/3/arithmetic/long.h | 187 +++++++++++++++++++++++++++++++--------
 include/ruby/3/attr/const.h      |  11 +++
 include/ruby/3/attr/constexpr.h  |  11 +++
 numeric.c                        |   2 +-
 4 files changed, 174 insertions(+), 37 deletions(-)

It also happens:

Assertion Failed: ./include/ruby/3/arithmetic/long.h:84:RB_INT2FIX:"(((i) < (9223372036854775807L / 2) + 1) && ((i) >= ((-9223372036854775807L -1L) / 2)))"

It doesn't look the real cause though, just revealed.
The cause was that hnum <<= 1; hnum = RSHIFT(hnum, 1); just clears/sets the MSB, but not the next bit, so it can exceed Fixnum limits.
I'm not sure why it didn't happen before the commit.

Actions #10

Updated by nobu (Nobuyoshi Nakada) over 1 year ago

  • Backport changed from 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN to 2.5: REQUIRED, 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED

Updated by naruse (Yui NARUSE) over 1 year ago

  • Backport changed from 2.5: REQUIRED, 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED to 2.5: REQUIRED, 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONE

ruby_3_0 b2beb8586e930c168af434d6545f75d76123192b.

Actions #12

Updated by nagachika (Tomoyuki Chikanaga) over 1 year ago

MEMO: backporting 5f6053824551aec947a1c53d08975595aca1e513,20a8425aa0f9a947e72b06cbd3a2afe9674dd18f but the test TestHash#test_any_hash_fixable and TestHash::TestSubHash#test_any_hash_fixable failed.

[11416/21074] TestHash#test_any_hash_fixable = 0.08 s
  1) Failure:
TestHash#test_any_hash_fixable [/Users/nagachika/opt/ruby-2.7/src/ruby_2_7/test/ruby/test_hash.rb:1853]:
Expected {"Int"=>true,
 "Float"=>true,
 "String"=>true,
 "Boolean"=>true,
 "WidgetFilter"=>true,
 "WidgetAggregation"=>true,
 "WidgetEdge"=>true,
 "WidgetSortOrder"=>true,
 "WidgetGrouping"=>true}.key?("Float") to return true.

[11552/21074] TestHash::TestSubHash#test_any_hash_fixable = 0.08 s
  2) Failure:
TestHash::TestSubHash#test_any_hash_fixable [/Users/nagachika/opt/ruby-2.7/src/ruby_2_7/test/ruby/test_hash.rb:1853]:
Expected {"Int"=>true,
 "Float"=>true,
 "String"=>true,
 "Boolean"=>true,
 "WidgetFilter"=>true,
 "WidgetAggregation"=>true,
 "WidgetEdge"=>true,
 "WidgetSortOrder"=>true,
 "WidgetGrouping"=>true}.key?("Int") to return true.

Updated by nagachika (Tomoyuki Chikanaga) over 1 year ago

  • Backport changed from 2.5: REQUIRED, 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONE to 2.5: REQUIRED, 2.6: REQUIRED, 2.7: DONTNEED, 3.0: DONE

I believe 20a8425aa0f9a947e72b06cbd3a2afe9674dd18f is not need to be backported into ruby_2_7, since the test test_any_hash_fixable passed without the patch to hash.c.

Actions

Also available in: Atom PDF