From f7d59dfe23b6fed5a6dc0720144eeaebb407efbb Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Mon, 8 Jul 2019 20:10:24 -0700 Subject: Add tests for Range#max and Range#min --- test/t/range.rb | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/test/t/range.rb b/test/t/range.rb index d71fe8946..7ce4a7a94 100644 --- a/test/t/range.rb +++ b/test/t/range.rb @@ -110,3 +110,45 @@ assert('Range#dup') do assert_equal r.end, "z" assert_true r.exclude_end? end + +assert('Range#max') do + assert_equal 10, (1..10).max + assert_equal 9, (1...10).max + assert_equal nil, (10..1).max + assert_equal nil, (10...1).max + + # equal endpoints + assert_equal 5, (5..5).max + assert_equal nil, (5...5).max + + # block overrides comparison + assert_equal(10, (1..10).max { |a, b| a <=> b }) + assert_equal(9, (1...10).max { |a, b| a <=> b }) + assert_equal(nil, (10..1).max { |a, b| a <=> b }) + assert_equal(nil, (10...1).max { |a, b| a <=> b }) + assert_equal(1, (1..10).max { |a, b| b <=> a }) + assert_equal(1, (1...10).max { |a, b| b <=> a }) + assert_equal(nil, (10..1).max { |a, b| b <=> a }) + assert_equal(nil, (10...1).max { |a, b| b <=> a }) +end + +assert('Range#min') do + assert_equal 1, (1..10).min + assert_equal 1, (1...10).min + assert_equal nil, (10..1).min + assert_equal nil, (10...1).min + + # equal endpoints + assert_equal 7, (7..7).min + assert_equal nil, (7...7).min + + # block overrides comparison + assert_equal(1, (1..10).min { |a, b| a <=> b }) + assert_equal(1, (1...10).min { |a, b| a <=> b }) + assert_equal(nil, (10..1).min { |a, b| a <=> b }) + assert_equal(nil, (10...1).min { |a, b| a <=> b }) + assert_equal(10, (1..10).min { |a, b| b <=> a }) + assert_equal(9, (1...10).min { |a, b| b <=> a }) + assert_equal(nil, (10..1).min { |a, b| b <=> a }) + assert_equal(nil, (10...1).min { |a, b| b <=> a }) +end -- cgit v1.2.3 From 469c6261c69999aab9e0d19cea6ac8e03f7847e3 Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Mon, 8 Jul 2019 22:35:12 -0700 Subject: Add tests for String Ranges Range#each depends on String#upto which is implemented in mruby-string-ext which is why these tests live there. --- mrbgems/mruby-string-ext/test/range.rb | 12 ++++++++++++ 1 file changed, 12 insertions(+) create mode 100644 mrbgems/mruby-string-ext/test/range.rb diff --git a/mrbgems/mruby-string-ext/test/range.rb b/mrbgems/mruby-string-ext/test/range.rb new file mode 100644 index 000000000..4b42cd3a6 --- /dev/null +++ b/mrbgems/mruby-string-ext/test/range.rb @@ -0,0 +1,12 @@ +assert('Range#max') do + # string Range depends on String#upto + assert_equal 'l', ('f'..'l').max + assert_equal 'e', ('a'...'f').max + assert_equal nil, ('z'..'l').max +end + +assert('Range#min') do + # string Range depends on String#upto + assert_equal 'f', ('f'..'l').min + assert_equal nil, ('z'..'l').min +end -- cgit v1.2.3 From 4085709ae1736fb755955d3d52b6b73c15853506 Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Mon, 8 Jul 2019 19:23:24 -0700 Subject: Specialize Enumerable#max and Enumerable#min for Range This patch prevents a hang for pathalogical (large) Ranges when computing max and min. Range inherits its implementation of max and min from Enumerable. Enumerable implements max and min by calling each. For Range objects, this is unnecessary since we know the max and the min by the end and begin attributes. It is also very slow. This code hangs unnecessarily: (0..2**32).max # ... hang (0..2**32).min # ... hang This patch overrides max and min after including enumerable to yield based on the begin and end methods. --- mrblib/range.rb | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 65 insertions(+), 1 deletion(-) diff --git a/mrblib/range.rb b/mrblib/range.rb index 392cc2274..746cb322c 100644 --- a/mrblib/range.rb +++ b/mrblib/range.rb @@ -15,7 +15,8 @@ class Range val = self.first last = self.last - if val.kind_of?(Fixnum) && last.kind_of?(Fixnum) # fixnums are special + # numerics are special + if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) lim = last lim += 1 unless exclude_end? i = val @@ -64,4 +65,67 @@ end # ISO 15.2.14.3 class Range include Enumerable + + def max(&block) + val = self.first + last = self.last + # numerics are special + if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) + return nil if val > last + return nil if val == last && exclude_end? + + max = last + max -= 1 if exclude_end? + max = val if block && block.call(val, last) > 0 + return max + end + + max = nil + each do |item| + max = + if max.nil? + item + elsif block && block.call(max, item) > 0 + item + elsif item > max + item + else + max + end + end + max + end + + def min(&block) + val = self.first + last = self.last + + # numerics are special + if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) + return nil if val > last + return nil if val == last && exclude_end? + + min = val + if block && block.call(val, last) > 0 + min = last + min -= 1 if exclude_end? + end + return min + end + + min = nil + each do |item| + min = + if min.nil? + item + elsif block && block.call(min, item) < 0 + item + elsif item < min + item + else + min + end + end + min + end end -- cgit v1.2.3 From d9c530379343ef0dd0f314c982ddeedea8eb1a60 Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Tue, 9 Jul 2019 01:40:44 -0700 Subject: Remove attempt at spec-compliant Range#max and Range#min from core --- mrblib/range.rb | 63 --------------------------------------------------------- test/t/range.rb | 42 -------------------------------------- 2 files changed, 105 deletions(-) diff --git a/mrblib/range.rb b/mrblib/range.rb index 746cb322c..3e6dbfb24 100644 --- a/mrblib/range.rb +++ b/mrblib/range.rb @@ -65,67 +65,4 @@ end # ISO 15.2.14.3 class Range include Enumerable - - def max(&block) - val = self.first - last = self.last - # numerics are special - if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) - return nil if val > last - return nil if val == last && exclude_end? - - max = last - max -= 1 if exclude_end? - max = val if block && block.call(val, last) > 0 - return max - end - - max = nil - each do |item| - max = - if max.nil? - item - elsif block && block.call(max, item) > 0 - item - elsif item > max - item - else - max - end - end - max - end - - def min(&block) - val = self.first - last = self.last - - # numerics are special - if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) - return nil if val > last - return nil if val == last && exclude_end? - - min = val - if block && block.call(val, last) > 0 - min = last - min -= 1 if exclude_end? - end - return min - end - - min = nil - each do |item| - min = - if min.nil? - item - elsif block && block.call(min, item) < 0 - item - elsif item < min - item - else - min - end - end - min - end end diff --git a/test/t/range.rb b/test/t/range.rb index 7ce4a7a94..d71fe8946 100644 --- a/test/t/range.rb +++ b/test/t/range.rb @@ -110,45 +110,3 @@ assert('Range#dup') do assert_equal r.end, "z" assert_true r.exclude_end? end - -assert('Range#max') do - assert_equal 10, (1..10).max - assert_equal 9, (1...10).max - assert_equal nil, (10..1).max - assert_equal nil, (10...1).max - - # equal endpoints - assert_equal 5, (5..5).max - assert_equal nil, (5...5).max - - # block overrides comparison - assert_equal(10, (1..10).max { |a, b| a <=> b }) - assert_equal(9, (1...10).max { |a, b| a <=> b }) - assert_equal(nil, (10..1).max { |a, b| a <=> b }) - assert_equal(nil, (10...1).max { |a, b| a <=> b }) - assert_equal(1, (1..10).max { |a, b| b <=> a }) - assert_equal(1, (1...10).max { |a, b| b <=> a }) - assert_equal(nil, (10..1).max { |a, b| b <=> a }) - assert_equal(nil, (10...1).max { |a, b| b <=> a }) -end - -assert('Range#min') do - assert_equal 1, (1..10).min - assert_equal 1, (1...10).min - assert_equal nil, (10..1).min - assert_equal nil, (10...1).min - - # equal endpoints - assert_equal 7, (7..7).min - assert_equal nil, (7...7).min - - # block overrides comparison - assert_equal(1, (1..10).min { |a, b| a <=> b }) - assert_equal(1, (1...10).min { |a, b| a <=> b }) - assert_equal(nil, (10..1).min { |a, b| a <=> b }) - assert_equal(nil, (10...1).min { |a, b| a <=> b }) - assert_equal(10, (1..10).min { |a, b| b <=> a }) - assert_equal(9, (1...10).min { |a, b| b <=> a }) - assert_equal(nil, (10..1).min { |a, b| b <=> a }) - assert_equal(nil, (10...1).min { |a, b| b <=> a }) -end -- cgit v1.2.3 From eab07daf92c9a8a2836923656d9e8f58583a52ba Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Tue, 9 Jul 2019 01:41:10 -0700 Subject: Add Range#max and Range#min tests from Ruby Spec --- mrbgems/mruby-range-ext/test/range.rb | 101 +++++++++++++++++++++++++++++++++ mrbgems/mruby-string-ext/test/range.rb | 18 +++++- 2 files changed, 117 insertions(+), 2 deletions(-) diff --git a/mrbgems/mruby-range-ext/test/range.rb b/mrbgems/mruby-range-ext/test/range.rb index efcbdabe4..6b135aeff 100644 --- a/mrbgems/mruby-range-ext/test/range.rb +++ b/mrbgems/mruby-range-ext/test/range.rb @@ -30,3 +30,104 @@ assert('Range#size') do assert_equal Float::INFINITY, (0..Float::INFINITY).size assert_nil ('a'..'z').size end + +assert('Range#max') do + # returns the maximum value in the range when called with no arguments + assert_equal 10, (1..10).max + assert_equal 9, (1...10).max + assert_equal 4294967295, (0...2**32).max + + # returns the maximum value in the Float range when called with no arguments + assert_equal 908.1111, (303.20..908.1111).max + + # raises TypeError when called on an exclusive range and a non Integer value + assert_raise(TypeError) { (303.20...908.1111).max } + + # returns nil when the endpoint is less than the start point + assert_equal nil, (100..10).max + + # returns nil when the endpoint equals the start point and the range is exclusive + assert_equal nil, (5...5).max + + # returns the endpoint when the endpoint equals the start point and the range is inclusive + assert_equal 5, (5..5).max + + # returns nil when the endpoint is less than the start point in a Float range + assert_equal nil, (3003.20..908.1111).max +end + +assert('Range#max given a block') do + # passes each pair of values in the range to the block + acc = [] + (1..10).max do |a, b| + acc << a + acc << b + a + end + (1..10).each do |value| + assert_true acc.include?(value) + end + + # passes each pair of elements to the block in reversed order + acc = [] + (1..5).max do |a, b| + acc << [a, b] + a + end + assert_equal [[2, 1], [3, 2], [4, 3], [5, 4]], acc + + # returns the element the block determines to be the maximum + assert_equal 1, ((1..3).max { |_a, _b| -3 }) + + # returns nil when the endpoint is less than the start point + assert_equal nil, ((100..10).max { |x, y| x <=> y }) + assert_equal nil, ((5...5).max { |x, y| x <=> y }) +end + +assert('Range#min') do + # returns the minimum value in the range when called with no arguments + assert_equal 1, (1..10).min + + # returns the minimum value in the Float range when called with no arguments + assert_equal 303.20, (303.20..908.1111).min + + # returns nil when the start point is greater than the endpoint + assert_equal nil, (100..10).min + + # returns nil when the endpoint equals the start point and the range is exclusive + assert_equal nil, (5...5).max + + # returns the endpoint when the endpoint equals the start point and the range is inclusive + assert_equal 5, (5..5).max + + # returns nil when the start point is greater than the endpoint in a Float range + assert_equal nil, (3003.20..908.1111).max +end + +assert('Range#min given a block') do + # passes each pair of values in the range to the block + acc = [] + (1..10).min do |a, b| + acc << a + acc << b + a + end + (1..10).each do |value| + assert_true acc.include?(value) + end + + # passes each pair of elements to the block in reversed order + acc = [] + (1..5).min do |a, b| + acc << [a, b] + a + end + assert_equal [[2, 1], [3, 1], [4, 1], [5, 1]], acc + + # returns the element the block determines to be the minimum + assert_equal 3, ((1..3).min { |_a, _b| -3 }) + + # returns nil when the start point is greater than the endpoint + assert_equal nil, ((100..10).min { |x, y| x <=> y }) + assert_equal nil, ((5...5).min { |x, y| x <=> y }) +end diff --git a/mrbgems/mruby-string-ext/test/range.rb b/mrbgems/mruby-string-ext/test/range.rb index 4b42cd3a6..80c286850 100644 --- a/mrbgems/mruby-string-ext/test/range.rb +++ b/mrbgems/mruby-string-ext/test/range.rb @@ -1,12 +1,26 @@ assert('Range#max') do - # string Range depends on String#upto + # returns the maximum value in the range when called with no arguments assert_equal 'l', ('f'..'l').max assert_equal 'e', ('a'...'f').max + + # returns nil when the endpoint is less than the start point assert_equal nil, ('z'..'l').max end +assert('Range#max given a block') do + # returns nil when the endpoint is less than the start point + assert_equal nil, (('z'..'l').max { |x, y| x <=> y }) +end + assert('Range#min') do - # string Range depends on String#upto + # returns the minimum value in the range when called with no arguments assert_equal 'f', ('f'..'l').min + + # returns nil when the start point is greater than the endpoint assert_equal nil, ('z'..'l').min end + +assert('Range#min given a block') do + # returns nil when the start point is greater than the endpoint + assert_equal nil, (('z'..'l').min { |x, y| x <=> y }) +end -- cgit v1.2.3 From 0ad5ba7a0f819cff87460d9b6f5691656ea75ade Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Tue, 9 Jul 2019 01:42:40 -0700 Subject: Add a fast path for Float and Fixnum ranges for Range#max and Range#min If no block is given and the Range has Fixnum or Float endpoints, do not iterate with each and instead compare the endpoints directly. This implementation passes all of the applicable specs from Ruby Spec. --- mrbgems/mruby-range-ext/mrblib/range.rb | 40 +++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/mrbgems/mruby-range-ext/mrblib/range.rb b/mrbgems/mruby-range-ext/mrblib/range.rb index de7925ba7..e09b2d096 100644 --- a/mrbgems/mruby-range-ext/mrblib/range.rb +++ b/mrbgems/mruby-range-ext/mrblib/range.rb @@ -25,4 +25,44 @@ class Range end ary end + + def max(&block) + val = self.first + last = self.last + return super if block + + # fast path for numerics + if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) + raise TypeError if exclude_end? && !last.kind_of?(Fixnum) + return nil if val > last + return nil if val == last && exclude_end? + + max = last + max -= 1 if exclude_end? + return max + end + + # delegate to Enumerable + super + end + + def min(&block) + val = self.first + last = self.last + return super if block + + # fast path for numerics + if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) + raise TypeError if exclude_end? && !last.kind_of?(Fixnum) + return nil if val > last + return nil if val == last && exclude_end? + + min = val + min -= 1 if exclude_end? + return min + end + + # delegate to Enumerable + super + end end -- cgit v1.2.3 From 56929362f58ba5ad3ebe4131a6cc4259e6479dc0 Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Tue, 9 Jul 2019 01:48:15 -0700 Subject: Fix Range#min fast path with exclusive range --- mrbgems/mruby-range-ext/mrblib/range.rb | 1 - mrbgems/mruby-range-ext/test/range.rb | 1 + 2 files changed, 1 insertion(+), 1 deletion(-) diff --git a/mrbgems/mruby-range-ext/mrblib/range.rb b/mrbgems/mruby-range-ext/mrblib/range.rb index e09b2d096..a149a57dc 100644 --- a/mrbgems/mruby-range-ext/mrblib/range.rb +++ b/mrbgems/mruby-range-ext/mrblib/range.rb @@ -58,7 +58,6 @@ class Range return nil if val == last && exclude_end? min = val - min -= 1 if exclude_end? return min end diff --git a/mrbgems/mruby-range-ext/test/range.rb b/mrbgems/mruby-range-ext/test/range.rb index 6b135aeff..b56d6b58e 100644 --- a/mrbgems/mruby-range-ext/test/range.rb +++ b/mrbgems/mruby-range-ext/test/range.rb @@ -87,6 +87,7 @@ end assert('Range#min') do # returns the minimum value in the range when called with no arguments assert_equal 1, (1..10).min + assert_equal 1, (1...10).min # returns the minimum value in the Float range when called with no arguments assert_equal 303.20, (303.20..908.1111).min -- cgit v1.2.3 From 3b77b5fd394f9c9ba841e7bea8ea62dc6e8a3a1b Mon Sep 17 00:00:00 2001 From: Ryan Lopopolo Date: Tue, 9 Jul 2019 02:08:14 -0700 Subject: Revert Float dependency in Range#each --- mrblib/range.rb | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/mrblib/range.rb b/mrblib/range.rb index 3e6dbfb24..392cc2274 100644 --- a/mrblib/range.rb +++ b/mrblib/range.rb @@ -15,8 +15,7 @@ class Range val = self.first last = self.last - # numerics are special - if (val.kind_of?(Fixnum) || val.kind_of?(Float)) && (last.kind_of?(Fixnum) || last.kind_of?(Float)) + if val.kind_of?(Fixnum) && last.kind_of?(Fixnum) # fixnums are special lim = last lim += 1 unless exclude_end? i = val -- cgit v1.2.3