[Feature #19839] Fix `Range#overlap?` for empty ranges

Empty ranges do not overlap with any range.

Regarding benchmarks, PR#8242 is significantly faster in some cases,
but one of these two cases is a wrong result.

|                           |ActiveSupport| PR#8242|built-ruby|
|:--------------------------|------------:|-------:|---------:|
|(2..3).overlap?(1..1)      |       7.761M| 15.053M|   32.368M|
|                           |            -|   1.94x|     4.17x|
|(2..3).overlap?(2..4)      |      25.720M| 55.070M|   21.981M|
|                           |        1.17x|   2.51x|         -|
|(2..3).overlap?(4..5)      |       7.616M| 15.048M|   21.730M|
|                           |            -|   1.98x|     2.85x|
|(2..3).overlap?(2..1)      |      25.585M| 56.545M|   32.786M|
|                           |            -|   2.21x|     1.28x|
|(2..3).overlap?(0..1)      |       7.554M| 14.755M|   32.545M|
|                           |            -|   1.95x|     4.31x|
|(2..3).overlap?(...1)      |       6.681M|  5.843M|   32.255M|
|                           |        1.14x|       -|     5.52x|
|(2...3).overlap?(..2)      |       6.676M|  5.817M|   21.572M|
|                           |        1.15x|       -|     3.71x|
|(2...3).overlap?(3...)     |       7.392M| 14.755M|   31.805M|
|                           |            -|   2.00x|     4.30x|
|(2..3).overlap?('a'..'d')  |       3.675M|  3.482M|   17.009M|
|                           |        1.06x|       -|     4.89x|

1 files changed, 72 insertions, 5 deletions

diff --git a/range.c b/range.c
index 946da0c4de..f8950f3f29 100644
--- a/range.c
+++ b/range.c
@@ -2151,6 +2151,18 @@ range_count(int argc, VALUE *argv, VALUE range)
     }
 }
 
+static bool
+empty_region_p(VALUE beg, VALUE end, int excl)
+{
+    if (NIL_P(beg)) return false;
+    if (NIL_P(end)) return false;
+    int less = r_less(beg, end);
+    /* empty range */
+    if (less > 0) return true;
+    if (excl && less == 0) return true;
+    return false;
+}
+
 /*
  *  call-seq:
  *    overlap?(range) -> true or false
@@ -2161,6 +2173,49 @@ range_count(int argc, VALUE *argv, VALUE range)
  *    (0..2).overlap?(3..4) #=> false
  *    (0..).overlap?(..0)   #=> true
  *
+ *  With non-range argument, raises TypeError.
+ *
+ *    (1..3).overlap?(1)         # TypeError
+ *
+ *  Returns +false+ if an internal call to <tt><=></tt> returns +nil+;
+ *  that is, the operands are not comparable.
+ *
+ *    (1..3).overlap?('a'..'d')  # => false
+ *
+ *  Returns +false+ if +self+ or +range+ is empty. "Empty range" means
+ *  that its begin value is larger than, or equal for an exclusive
+ *  range, its end value.
+ *
+ *    (4..1).overlap?(2..3)      # => false
+ *    (4..1).overlap?(..3)       # => false
+ *    (4..1).overlap?(2..)       # => false
+ *    (2...2).overlap?(1..2)     # => false
+ *
+ *    (1..4).overlap?(3..2)      # => false
+ *    (..4).overlap?(3..2)       # => false
+ *    (1..).overlap?(3..2)       # => false
+ *    (1..2).overlap?(2...2)     # => false
+ *
+ *  Returns +false+ if the begin value one of +self+ and +range+ is
+ *  larger than, or equal if the other is an exclusive range, the end
+ *  value of the other:
+ *
+ *    (4..5).overlap?(2..3)      # => false
+ *    (4..5).overlap?(2...4)     # => false
+ *
+ *    (1..2).overlap?(3..4)      # => false
+ *    (1...3).overlap?(3..4)     # => false
+ *
+ *  Returns +false+ if the end value one of +self+ and +range+ is
+ *  larger than, or equal for an exclusive range, the end value of the
+ *  other:
+ *
+ *    (4..5).overlap?(2..3)      # => false
+ *    (4..5).overlap?(2...4)     # => false
+ *
+ *    (1..2).overlap?(3..4)      # => false
+ *    (1...3).overlap?(3..4)     # => false
+ *
  *  Related: Range#cover?.
  */
 
@@ -2168,15 +2223,27 @@ static VALUE
 range_overlap(VALUE range, VALUE other)
 {
     if (!rb_obj_is_kind_of(other, rb_cRange)) {
-        rb_raise(rb_eTypeError, "argument must be Range");
+        rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE" (expected Range)",
+                 rb_class_name(rb_obj_class(other)));
     }
 
-    VALUE beg_self, beg_other;
+    VALUE self_beg = RANGE_BEG(range);
+    VALUE self_end = RANGE_END(range);
+    int self_excl = EXCL(range);
+    VALUE other_beg = RANGE_BEG(other);
+    VALUE other_end = RANGE_END(other);
+    int other_excl = EXCL(other);
+
+    if (empty_region_p(self_beg, other_end, other_excl)) return Qfalse;
+    if (empty_region_p(other_beg, self_end, self_excl)) return Qfalse;
 
-    beg_self = RANGE_BEG(range);
-    beg_other = RANGE_BEG(other);
+    /* if both begin values are equal, no more comparisons needed */
+    if (rb_equal(self_beg, other_beg)) return Qtrue;
 
-    return RBOOL(rb_equal(beg_self, beg_other) || range_cover(range, beg_other) || range_cover(other, beg_self));
+    if (empty_region_p(self_beg, self_end, self_excl)) return Qfalse;
+    if (empty_region_p(other_beg, other_end, other_excl)) return Qfalse;
+
+    return Qtrue;
 }
 
 /* A \Range object represents a collection of values