Add Range#reverse_each implementation for performance

2 files changed, 271 insertions, 0 deletions

diff --git a/range.c b/range.c
index e57ffef7e5..867c96336a 100644
--- a/range.c
+++ b/range.c
@@ -1024,6 +1024,139 @@ range_each(VALUE range)
     return range;
 }
 
+RBIMPL_ATTR_NORETURN()
+static void
+range_reverse_each_bignum_beginless(VALUE end)
+{
+    RUBY_ASSERT(RBIGNUM_NEGATIVE_P(end));
+
+    for (;; end = rb_big_minus(end, INT2FIX(1))) {
+        rb_yield(end);
+    }
+    UNREACHABLE;
+}
+
+static void
+range_reverse_each_bignum(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(RBIGNUM_POSITIVE_P(beg) == RBIGNUM_POSITIVE_P(end));
+
+    VALUE c;
+    while ((c = rb_big_cmp(beg, end)) != INT2FIX(1)) {
+        rb_yield(end);
+        if (c == INT2FIX(0)) break;
+        end = rb_big_minus(end, INT2FIX(1));
+    }
+}
+
+static void
+range_reverse_each_positive_bignum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (FIXNUM_P(end) || RBIGNUM_NEGATIVE_P(end)) return;
+
+    if (NIL_P(beg) || FIXNUM_P(beg) || RBIGNUM_NEGATIVE_P(beg)) {
+        beg = LONG2NUM(FIXNUM_MAX + 1);
+    }
+
+    range_reverse_each_bignum(beg, end);
+}
+
+static void
+range_reverse_each_fixnum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (!FIXNUM_P(beg)) {
+        if (!NIL_P(beg) && RBIGNUM_POSITIVE_P(beg)) return;
+
+        beg = LONG2FIX(FIXNUM_MIN);
+    }
+
+    if (!FIXNUM_P(end)) {
+        if (RBIGNUM_NEGATIVE_P(end)) return;
+
+        end = LONG2FIX(FIXNUM_MAX);
+    }
+
+    long b = FIX2LONG(beg);
+    long e = FIX2LONG(end);
+    for (long i = e; i >= b; --i) {
+        rb_yield(LONG2FIX(i));
+    }
+}
+
+static void
+range_reverse_each_negative_bignum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (FIXNUM_P(end) || RBIGNUM_POSITIVE_P(end)) {
+        end = LONG2NUM(FIXNUM_MIN - 1);
+    }
+
+    if (NIL_P(beg)) {
+        range_reverse_each_bignum_beginless(end);
+    }
+
+    if (FIXNUM_P(beg) || RBIGNUM_POSITIVE_P(beg)) return;
+
+    range_reverse_each_bignum(beg, end);
+}
+
+/*
+ *  call-seq:
+ *    reverse_each {|element| ... } -> self
+ *    reverse_each                  -> an_enumerator
+ *
+ *  With a block given, passes each element of +self+ to the block in reverse order:
+ *
+ *    a = []
+ *    (1..4).reverse_each {|element| a.push(element) } # => 1..4
+ *    a # => [4, 3, 2, 1]
+ *
+ *    a = []
+ *    (1...4).reverse_each {|element| a.push(element) } # => 1...4
+ *    a # => [3, 2, 1]
+ *
+ *  With no block given, returns an enumerator.
+ *
+ */
+
+static VALUE
+range_reverse_each(VALUE range)
+{
+    RETURN_SIZED_ENUMERATOR(range, 0, 0, range_enum_size);
+
+    VALUE beg = RANGE_BEG(range);
+    VALUE end = RANGE_END(range);
+    int excl = EXCL(range);
+
+    if (FIXNUM_P(beg) && FIXNUM_P(end)) {
+        if (excl) {
+            if (end == LONG2FIX(FIXNUM_MIN)) return range;
+
+            end = rb_int_minus(end, INT2FIX(1));
+        }
+
+        range_reverse_each_fixnum_section(beg, end);
+    }
+    else if ((NIL_P(beg) || RB_INTEGER_TYPE_P(beg)) && RB_INTEGER_TYPE_P(end)) {
+        if (excl) {
+            end = rb_int_minus(end, INT2FIX(1));
+        }
+        range_reverse_each_positive_bignum_section(beg, end);
+        range_reverse_each_fixnum_section(beg, end);
+        range_reverse_each_negative_bignum_section(beg, end);
+    }
+    else {
+        return rb_call_super(0, NULL);
+    }
+
+    return range;
+}
+
 /*
  *  call-seq:
  *    self.begin -> object
@@ -2529,6 +2662,7 @@ Init_Range(void)
     rb_define_method(rb_cRange, "each", range_each, 0);
     rb_define_method(rb_cRange, "step", range_step, -1);
     rb_define_method(rb_cRange, "%", range_percent_step, 1);
+    rb_define_method(rb_cRange, "reverse_each", range_reverse_each, 0);
     rb_define_method(rb_cRange, "bsearch", range_bsearch, 0);
     rb_define_method(rb_cRange, "begin", range_begin, 0);
     rb_define_method(rb_cRange, "end", range_end, 0);
diff --git a/test/ruby/test_range.rb b/test/ruby/test_range.rb
index a09108f806..8228b6cfbe 100644
--- a/test/ruby/test_range.rb
+++ b/test/ruby/test_range.rb
@@ -496,6 +496,143 @@ class TestRange < Test::Unit::TestCase
     assert_equal([0, 1, 2, 3, 4], result)
   end
 
+  def test_reverse_each
+    a = []
+    (1..3).reverse_each {|x| a << x }
+    assert_equal([3, 2, 1], a)
+
+    a = []
+    (1...3).reverse_each {|x| a << x }
+    assert_equal([2, 1], a)
+
+    fmax = RbConfig::LIMITS['FIXNUM_MAX']
+    fmin = RbConfig::LIMITS['FIXNUM_MIN']
+
+    a = []
+    (fmax+1..fmax+3).reverse_each {|x| a << x }
+    assert_equal([fmax+3, fmax+2, fmax+1], a)
+
+    a = []
+    (fmax+1...fmax+3).reverse_each {|x| a << x }
+    assert_equal([fmax+2, fmax+1], a)
+
+    a = []
+    (fmax-1..fmax+1).reverse_each {|x| a << x }
+    assert_equal([fmax+1, fmax, fmax-1], a)
+
+    a = []
+    (fmax-1...fmax+1).reverse_each {|x| a << x }
+    assert_equal([fmax, fmax-1], a)
+
+    a = []
+    (fmin-1..fmin+1).reverse_each{|x| a << x }
+    assert_equal([fmin+1, fmin, fmin-1], a)
+
+    a = []
+    (fmin-1...fmin+1).reverse_each{|x| a << x }
+    assert_equal([fmin, fmin-1], a)
+
+    a = []
+    (fmin-3..fmin-1).reverse_each{|x| a << x }
+    assert_equal([fmin-1, fmin-2, fmin-3], a)
+
+    a = []
+    (fmin-3...fmin-1).reverse_each{|x| a << x }
+    assert_equal([fmin-2, fmin-3], a)
+
+    a = []
+    ("a".."c").reverse_each {|x| a << x }
+    assert_equal(["c", "b", "a"], a)
+  end
+
+  def test_reverse_each_for_beginless_range
+    fmax = RbConfig::LIMITS['FIXNUM_MAX']
+    fmin = RbConfig::LIMITS['FIXNUM_MIN']
+
+    a = []
+    (..3).reverse_each {|x| a << x; break if x <= 0 }
+    assert_equal([3, 2, 1, 0], a)
+
+    a = []
+    (...3).reverse_each {|x| a << x; break if x <= 0 }
+    assert_equal([2, 1, 0], a)
+
+    a = []
+    (..fmax+1).reverse_each {|x| a << x; break if x <= fmax-1 }
+    assert_equal([fmax+1, fmax, fmax-1], a)
+
+    a = []
+    (...fmax+1).reverse_each {|x| a << x; break if x <= fmax-1 }
+    assert_equal([fmax, fmax-1], a)
+
+    a = []
+    (..fmin+1).reverse_each {|x| a << x; break if x <= fmin-1 }
+    assert_equal([fmin+1, fmin, fmin-1], a)
+
+    a = []
+    (...fmin+1).reverse_each {|x| a << x; break if x <= fmin-1 }
+    assert_equal([fmin, fmin-1], a)
+
+    a = []
+    (..fmin-1).reverse_each {|x| a << x; break if x <= fmin-3 }
+    assert_equal([fmin-1, fmin-2, fmin-3], a)
+
+    a = []
+    (...fmin-1).reverse_each {|x| a << x; break if x <= fmin-3 }
+    assert_equal([fmin-2, fmin-3], a)
+  end
+
+  def test_reverse_each_for_single_point_range
+    fmin = RbConfig::LIMITS['FIXNUM_MIN']
+    fmax = RbConfig::LIMITS['FIXNUM_MAX']
+
+    values = [fmin*2, fmin-1, fmin, 0, fmax, fmax+1, fmax*2]
+
+    values.each do |b|
+      r = b..b
+      a = []
+      r.reverse_each {|x| a << x }
+      assert_equal([b], a, "failed on #{r}")
+
+      r = b...b+1
+      a = []
+      r.reverse_each {|x| a << x }
+      assert_equal([b], a, "failed on #{r}")
+    end
+  end
+
+  def test_reverse_each_for_empty_range
+    fmin = RbConfig::LIMITS['FIXNUM_MIN']
+    fmax = RbConfig::LIMITS['FIXNUM_MAX']
+
+    values = [fmin*2, fmin-1, fmin, 0, fmax, fmax+1, fmax*2]
+
+    values.each do |b|
+      r = b..b-1
+      a = []
+      r.reverse_each {|x| a << x }
+      assert_equal([], a, "failed on #{r}")
+    end
+
+    values.repeated_permutation(2).to_a.product([true, false]).each do |(b, e), excl|
+      next unless b > e || (b == e && excl)
+
+      r = Range.new(b, e, excl)
+      a = []
+      r.reverse_each {|x| a << x }
+      assert_equal([], a, "failed on #{r}")
+    end
+  end
+
+  def test_reverse_each_with_no_block
+    enum = (1..5).reverse_each
+    assert_equal 5, enum.size
+
+    a = []
+    enum.each {|x| a << x }
+    assert_equal [5, 4, 3, 2, 1], a
+  end
+
   def test_begin_end
     assert_equal(0, (0..1).begin)
     assert_equal(1, (0..1).end)