Introduce beginless range [Feature#14799]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@67422 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

8 files changed, 123 insertions, 19 deletions

diff --git a/NEWS b/NEWS
index efdc1d917f..54a180a196 100644
--- a/NEWS
+++ b/NEWS
@@ -28,6 +28,12 @@ sufficient information, see the ChangeLog file or Redmine
 * Numbered parameter as the default block parameter is introduced as an
   experimental feature.  [Feature #4475]
 
+* A beginless range is experimentally introduced.  It might not be as useful
+  as an endless range, but would be good for DSL purpose.
+
+     ary[..3]  # identical to ary[0..3]
+     where(sales: ..100)
+
 === Core classes updates (outstanding ones only)
 
 Enumerable::
diff --git a/defs/id.def b/defs/id.def
index 9ab9af950d..91a9768ad6 100644
--- a/defs/id.def
+++ b/defs/id.def
@@ -76,6 +76,8 @@ firstline, predefined = __LINE__+1, %[\
 token_ops = %[\
   Dot2          ..      DOT2
   Dot3          ...     DOT3
+  BDot2         ..      BDOT2
+  BDot3         ...     BDOT3
   UPlus         +@      UPLUS
   UMinus        -@      UMINUS
   Pow           **      POW
diff --git a/doc/syntax/literals.rdoc b/doc/syntax/literals.rdoc
index 08eefd21de..ecf7d62a2a 100644
--- a/doc/syntax/literals.rdoc
+++ b/doc/syntax/literals.rdoc
@@ -334,6 +334,7 @@ its ending value.
   (1..2)  # includes its ending value
   (1...2) # excludes its ending value
   (1..)   # endless range, representing infinite sequence from 1 to Infinity
+  (..1)   # beginless range, representing infinite sequence from -Infinity to 1
 
 You may create a range of any object.  See the Range documentation for details
 on the methods you need to implement.
diff --git a/parse.y b/parse.y
index bc7fedb436..ff4fe986fe 100644
--- a/parse.y
+++ b/parse.y
@@ -922,6 +922,8 @@ static void token_info_warn(struct parser_params *p, const char *token, token_in
 %token tNMATCH		RUBY_TOKEN(NMATCH) "!~"
 %token tDOT2		RUBY_TOKEN(DOT2)   ".."
 %token tDOT3		RUBY_TOKEN(DOT3)   "..."
+%token tBDOT2		RUBY_TOKEN(BDOT2)   "(.."
+%token tBDOT3		RUBY_TOKEN(BDOT3)   "(..."
 %token tAREF		RUBY_TOKEN(AREF)   "[]"
 %token tASET		RUBY_TOKEN(ASET)   "[]="
 %token tLSHFT		RUBY_TOKEN(LSHFT)  "<<"
@@ -968,7 +970,7 @@ static void token_info_warn(struct parser_params *p, const char *token, token_in
 %right '=' tOP_ASGN
 %left modifier_rescue
 %right '?' ':'
-%nonassoc tDOT2 tDOT3
+%nonassoc tDOT2 tDOT3 tBDOT2 tBDOT3
 %left  tOROP
 %left  tANDOP
 %nonassoc  tCMP tEQ tEQQ tNEQ tMATCH tNMATCH
@@ -1996,6 +1998,30 @@ arg		: lhs '=' arg_rhs
 		    /*% %*/
 		    /*% ripper: dot3!($1, Qnil) %*/
 		    }
+		| tBDOT2 arg
+		    {
+		    /*%%%*/
+                        YYLTYPE loc;
+                        loc.beg_pos = @1.beg_pos;
+                        loc.end_pos = @1.beg_pos;
+
+			value_expr($2);
+			$$ = NEW_DOT2(new_nil(&loc), $2, &@$);
+		    /*% %*/
+		    /*% ripper: dot2!(Qnil, $2) %*/
+		    }
+		| tBDOT3 arg
+		    {
+		    /*%%%*/
+                        YYLTYPE loc;
+                        loc.beg_pos = @1.beg_pos;
+                        loc.end_pos = @1.beg_pos;
+
+			value_expr($2);
+			$$ = NEW_DOT3(new_nil(&loc), $2, &@$);
+		    /*% %*/
+		    /*% ripper: dot3!(Qnil, $2) %*/
+		    }
 		| arg '+' arg
 		    {
 			$$ = call_bin_op(p, $1, '+', $3, &@2, &@$);
@@ -8241,15 +8267,16 @@ parser_yylex(struct parser_params *p)
 	pushback(p, c);
 	return warn_balanced('-', "-", "unary operator");
 
-      case '.':
+      case '.': {
+        int is_beg = IS_BEG();
 	SET_LEX_STATE(EXPR_BEG);
 	switch (c = nextc(p)) {
 	  case '.':
 	    if ((c = nextc(p)) == '.') {
-		return tDOT3;
+		return is_beg ? tBDOT3 : tDOT3;
 	    }
 	    pushback(p, c);
-	    return tDOT2;
+	    return is_beg ? tBDOT2 : tDOT2;
 	  case ':':
 	    switch (c = nextc(p)) {
 	      default:
@@ -8275,6 +8302,7 @@ parser_yylex(struct parser_params *p)
 	set_yylval_id('.');
 	SET_LEX_STATE(EXPR_DOT);
 	return '.';
+      }
 
       case '0': case '1': case '2': case '3': case '4':
       case '5': case '6': case '7': case '8': case '9':
diff --git a/range.c b/range.c
index 22cf237fc1..6895511e59 100644
--- a/range.c
+++ b/range.c
@@ -35,7 +35,7 @@ static VALUE r_cover_p(VALUE, VALUE, VALUE, VALUE);
 static void
 range_init(VALUE range, VALUE beg, VALUE end, VALUE exclude_end)
 {
-    if ((!FIXNUM_P(beg) || !FIXNUM_P(end)) && !NIL_P(end)) {
+    if ((!FIXNUM_P(beg) || !FIXNUM_P(end)) && !NIL_P(beg) && !NIL_P(end)) {
 	VALUE v;
 
 	v = rb_funcall(beg, id_cmp, 1, end);
@@ -704,8 +704,8 @@ range_bsearch(VALUE range)
     }
 #if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T)
     else if (RB_TYPE_P(beg, T_FLOAT) || RB_TYPE_P(end, T_FLOAT)) {
-	int64_t low  = double_as_int64(RFLOAT_VALUE(rb_Float(beg)));
-	int64_t high = double_as_int64(NIL_P(end) ? HUGE_VAL : RFLOAT_VALUE(rb_Float(end)));
+	int64_t low  = double_as_int64(NIL_P(beg) ? -HUGE_VAL : RFLOAT_VALUE(rb_Float(beg)));
+	int64_t high = double_as_int64(NIL_P(end) ?  HUGE_VAL : RFLOAT_VALUE(rb_Float(end)));
 	int64_t mid, org_high;
 	BSEARCH(int64_as_double_to_num);
     }
@@ -726,6 +726,18 @@ range_bsearch(VALUE range)
 	    diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
 	}
     }
+    else if (NIL_P(beg) && is_integer_p(end)) {
+	VALUE diff = LONG2FIX(-1);
+	RETURN_ENUMERATOR(range, 0, 0);
+	while (1) {
+	    VALUE mid = rb_funcall(end, '+', 1, diff);
+	    BSEARCH_CHECK(mid);
+	    if (!smaller) {
+		return bsearch_integer_range(mid, end, 0);
+	    }
+	    diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
+	}
+    }
     else {
 	rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg));
     }
@@ -770,6 +782,9 @@ range_size(VALUE range)
             return DBL2NUM(HUGE_VAL);
         }
     }
+    else if (NIL_P(b)) {
+        return DBL2NUM(HUGE_VAL);
+    }
 
     return Qnil;
 }
@@ -1230,7 +1245,7 @@ rb_range_beg_len(VALUE range, long *begp, long *lenp, long len, int err)
 
     if (!rb_range_values(range, &b, &e, &excl))
 	return Qfalse;
-    beg = NUM2LONG(b);
+    beg = NIL_P(b) ? 0 : NUM2LONG(b);
     end = NIL_P(e) ? -1 : NUM2LONG(e);
     if (NIL_P(e)) excl = 0;
     origbeg = beg;
@@ -1392,6 +1407,12 @@ range_include_internal(VALUE range, VALUE val)
 	    VALUE rb_str_include_range_p(VALUE beg, VALUE end, VALUE val, VALUE exclusive);
 	    return rb_str_include_range_p(beg, end, val, RANGE_EXCL(range));
 	}
+        else if (NIL_P(beg)) {
+	    VALUE r = rb_funcall(val, id_cmp, 1, end);
+	    if (NIL_P(r)) return Qfalse;
+	    if (rb_cmpint(r, val, end) <= 0) return Qtrue;
+	    return Qfalse;
+        }
 	else if (NIL_P(end)) {
 	    VALUE r = rb_funcall(beg, id_cmp, 1, val);
 	    if (NIL_P(r)) return Qfalse;
@@ -1487,7 +1508,7 @@ r_cover_range_p(VALUE range, VALUE beg, VALUE end, VALUE val)
 static VALUE
 r_cover_p(VALUE range, VALUE beg, VALUE end, VALUE val)
 {
-    if (r_less(beg, val) <= 0) {
+    if (NIL_P(beg) || r_less(beg, val) <= 0) {
 	int excl = EXCL(range);
 	if (NIL_P(end) || r_less(val, end) <= -excl)
 	    return Qtrue;
@@ -1550,9 +1571,15 @@ range_alloc(VALUE klass)
  *     ('a'..'e').to_a    #=> ["a", "b", "c", "d", "e"]
  *     ('a'...'e').to_a   #=> ["a", "b", "c", "d"]
  *
- *  == Endless Ranges
+ *  == Beginless/Endless Ranges
+ *
+ *  A "beginless range" and "endless range" represents a semi-infinite
+ *  range.  Literal notation for a beginless range is:
+ *
+ *     (..1)
+ *     # or
+ *     (...1)
  *
- *  An "endless range" represents a semi-infinite range.
  *  Literal notation for an endless range is:
  *
  *     (1..)
@@ -1564,14 +1591,16 @@ range_alloc(VALUE klass)
  *     (1..nil)  # or similarly (1...nil)
  *     Range.new(1, nil) # or Range.new(1, nil, true)
  *
- *  Endless ranges are useful, for example, for idiomatic slicing of
- *  arrays:
+ *  Beginless/endless ranges are useful, for example, for idiomatic
+ *  slicing of arrays:
  *
+ *    [1, 2, 3, 4, 5][...2]   # => [1, 2]
  *    [1, 2, 3, 4, 5][2...]   # => [3, 4, 5]
  *
  *  Some implementation details:
  *
- *  * +end+ of endless range is +nil+;
+ *  * +begin+ of beginless range and +end+ of endless range are +nil+;
+ *  * +each+ of beginless range raises an exception;
  *  * +each+ of endless range enumerates infinite sequence (may be
  *    useful in combination with Enumerable#take_while or similar
  *    methods);
diff --git a/spec/ruby/core/range/new_spec.rb b/spec/ruby/core/range/new_spec.rb
index c110687163..367511742c 100644
--- a/spec/ruby/core/range/new_spec.rb
+++ b/spec/ruby/core/range/new_spec.rb
@@ -43,9 +43,25 @@ describe "Range.new" do
     end
   end
 
-  describe "endless range" do
-    it "does not allow range without left boundary" do
-      -> { Range.new(nil, 1) }.should raise_error(ArgumentError, /bad value for range/)
+  describe "beginless/endless range" do
+    ruby_version_is ""..."2.7" do
+      it "does not allow range without left boundary" do
+        -> { Range.new(nil, 1) }.should raise_error(ArgumentError, /bad value for range/)
+      end
+    end
+
+    ruby_version_is "2.7" do
+      it "allows beginless left boundary" do
+        range = Range.new(nil, 1)
+        range.begin.should == nil
+      end
+
+      it "distinguishes ranges with included and excluded right boundary" do
+        range_exclude = Range.new(nil, 1, true)
+        range_include = Range.new(nil, 1, false)
+
+        range_exclude.should_not == range_include
+      end
     end
 
     ruby_version_is ""..."2.6" do
diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
index b61bac03c2..8bb9288822 100644
--- a/test/ruby/test_array.rb
+++ b/test/ruby/test_array.rb
@@ -42,6 +42,8 @@ class TestArray < Test::Unit::TestCase
     assert_equal([1, 2, 3], x[1..3])
     assert_equal([1, 2, 3], x[1,3])
     assert_equal([3, 4, 5], x[3..])
+    assert_equal([0, 1, 2], x[..2])
+    assert_equal([0, 1], x[...2])
 
     x[0, 2] = 10
     assert_equal([10, 2, 3, 4, 5], x)
@@ -375,8 +377,11 @@ class TestArray < Test::Unit::TestCase
 
     assert_equal(@cls[10, 11, 12], a[9..11])
     assert_equal(@cls[98, 99, 100], a[97..])
+    assert_equal(@cls[1, 2, 3], a[..2])
+    assert_equal(@cls[1, 2], a[...2])
     assert_equal(@cls[10, 11, 12], a[-91..-89])
-    assert_equal(@cls[98, 99, 100], a[-3..])
+    assert_equal(@cls[1, 2, 3], a[..-98])
+    assert_equal(@cls[1, 2], a[...-98])
 
     assert_nil(a[10, -3])
     assert_equal [], a[10..7]
@@ -462,6 +467,14 @@ class TestArray < Test::Unit::TestCase
     assert_equal(nil, a[10..] = nil)
     assert_equal(@cls[*(0..9).to_a] + @cls[nil], a)
 
+    a = @cls[*(0..99).to_a]
+    assert_equal(nil, a[..10] = nil)
+    assert_equal(@cls[nil] + @cls[*(11..99).to_a], a)
+
+    a = @cls[*(0..99).to_a]
+    assert_equal(nil, a[...10] = nil)
+    assert_equal(@cls[nil] + @cls[*(10..99).to_a], a)
+
     a = @cls[1, 2, 3]
     a[1, 0] = a
     assert_equal([1, 1, 2, 3, 2, 3], a)
diff --git a/test/ruby/test_range.rb b/test/ruby/test_range.rb
index 6a2081fcd2..6c1761f3b0 100644
--- a/test/ruby/test_range.rb
+++ b/test/ruby/test_range.rb
@@ -691,6 +691,8 @@ class TestRange < Test::Unit::TestCase
 
     assert_equal Float::INFINITY, (1...).size
     assert_equal Float::INFINITY, (1.0...).size
+    assert_equal Float::INFINITY, (...1).size
+    assert_equal Float::INFINITY, (...1.0).size
     assert_nil ("a"...).size
   end
 
@@ -735,6 +737,7 @@ class TestRange < Test::Unit::TestCase
     assert_equal(1, (0...ary.size).bsearch {|i| ary[i] >= 100 })
 
     assert_equal(1_000_001, (0...).bsearch {|i| i > 1_000_000 })
+    assert_equal( -999_999, (...0).bsearch {|i| i > -1_000_000 })
   end
 
   def test_bsearch_for_float
@@ -787,7 +790,8 @@ class TestRange < Test::Unit::TestCase
     assert_in_delta(1.0, (0.0..inf).bsearch {|x| Math.log(x) >= 0 })
     assert_in_delta(7.0, (0.0..10).bsearch {|x| 7.0 - x })
 
-    assert_equal(1_000_000.0.next_float, (0.0..).bsearch {|x| x > 1_000_000 })
+    assert_equal( 1_000_000.0.next_float, (0.0..).bsearch {|x| x > 1_000_000 })
+    assert_equal(-1_000_000.0.next_float, (..0.0).bsearch {|x| x > -1_000_000 })
   end
 
   def check_bsearch_values(range, search, a)
@@ -890,6 +894,7 @@ class TestRange < Test::Unit::TestCase
     assert_equal(bignum + 0, (bignum...bignum+ary.size).bsearch {|i| true })
     assert_equal(nil, (bignum...bignum+ary.size).bsearch {|i| false })
     assert_equal(bignum * 2 + 1, (bignum...).bsearch {|i| i > bignum * 2 })
+    assert_equal(-bignum * 2 + 1, (...-bignum).bsearch {|i| i > -bignum * 2 })
 
     assert_raise(TypeError) { ("a".."z").bsearch {} }
   end
@@ -907,4 +912,8 @@ class TestRange < Test::Unit::TestCase
     assert_equal([1,2,3,4], (1...5).to_a)
     assert_raise(RangeError) { (1..).to_a }
   end
+
+  def test_beginless_range_iteration
+    assert_raise(TypeError) { (..1).each { } }
+  end
 end