Overflow condition of `Range(Int, Int)#bsearch`

[HertzDevil]

The midpoint between two endpoints in Range#bsearch is computed as from + ((to - from) >> 1). This overflows if both from and to are the same signed integer type:

(-100_i8..100_i8).bsearch { true }        # Arithmetic overflow (OverflowError)
(Int32::MIN..Int32::MAX).bsearch { true } # Arithmetic overflow (OverflowError)

as 200 and 0xFFFFFFFF do not fit into an Int8 or an Int32 respectively. These calls of course should never raise, because the midpoint of two integers of the same type is guaranteed to fit into that type's range (after truncation).

The situation is more complicated if the two endpoints' types are different:

(Int8::MIN..UInt8::MAX).bsearch(&.>= -100) # -100?
(Int8::MIN..UInt8::MAX).bsearch(&.>= 200)  # 200?

If these values were Int32, the first call would yield 63 then -33, and the second call would yield 63 then 159. If we fix the yielded value's type to either Int8 or UInt8, then an overflow would always happen. We should decide a sensible behavior here:

• Since any two integer types will overlap in range, any two values' midpoint will also fit into at least one type's range. Always try to find that type. The block must therefore accept a B | E. (This would also apply to Fix float number overflow in range rand method #13825, actually.)
• Specify that only values fitting into B's range are allowed; if any midpoint exceeds B's range, raise OverflowError even if a valid first element within B's range exists. The block then accepts a B, similar to Indexable#bsearch.

Extra union types in B and E should not matter; (1_i8.as(Int8 | Int32)..10_u8.as(UInt8 | UInt32)).bsearch will only ever yield Int8 | UInt8s, never an Int32 nor UInt32.

[straight-shoota]

I'm starting to wonder about actual use cases for Range(B, E) where B != E. Apart from Nil, I don't see much use. If you want to represent a numerical range, it should not be too much to expect that both, begin and end, are using the same type.

[HertzDevil]

It appears that Range(T) was attempted at least once, and then reverted. If I add the following:

struct Range(B, E)
  def initialize(@begin : B, @end : E, @exclusive : Bool = false)
    {% raise "" unless B == E || B == Nil || E == Nil || B == E? || E == B? %}
  end
end

and also skip Range's unit tests, then only the following raises from make std_spec crystal:

crystal/src/socket/address.cr

Lines 702 to 704 in c97c20e

	def self.valid_port?(port : Int) : Bool
	port.in?(0..UInt16::MAX)
	end

If I omit the last two cases, then snippets like this also raise:

crystal/src/uri.cr

Lines 457 to 467 in c97c20e

	private def resolve_path(path : String, base : String) : String
	unless path.starts_with?('/')
	if path.empty?
	path = base
	elsif !base.empty?
	out_base = base.ends_with?('/') ? base : base[0..base.rindex('/')]
	path = String.interpolation(out_base, path)
	end
	end
	remove_dot_segments(path)
	end

Here rindex returns an Int32?, and I think that doesn't hurt. Maybe with some overloading tricks we could turn a Range(Int32, Int32 | Nil) into a Range(Int32, Int32) | Range(Int32, Nil); either approach has its own caveats.

The above check is not sufficient to address this issue though; if (Int8::MIN..UInt8::MAX).bsearch breaks, (Int8::MIN.as(Int8 | UInt8)..UInt8::MAX.as(Int8 | UInt8)).bsearch will break in the same way, even though it is a Range(Int8 | UInt8, Int8 | UInt8).

[straight-shoota]

Yeah I'm not up for any immediate action upon Range with differing types. I'm just questioning whether we should put any effort in handling them in implementations such as #bsearch. They're pretty much edge cases and I'd be totally fine if #bsearch wouldn't compile with different types. This should probably be a compile time error though.

The runtime overflow with same type values needs to be fixed, of course.

[compumike]

If it is helpful, for the same-integer-type case, there is a bitwise implementation that is overflow-safe:

def mid(from, to)
  # Only safe if from and to are the exact same integer type!
  (from & to) + ((from ^ to) >> 1)
end

For example:

mid(-100_i8, 100_i8) => 0
mid(Int8::MIN, Int8::MAX) => -1
mid(Int8::MIN, Int8::MIN) => -128
mid(Int8::MAX, Int8::MAX) => 127
mid(UInt8::MIN, UInt8::MAX) => 127
mid(UInt8::MIN, UInt8::MIN) => 0
mid(UInt8::MAX, UInt8::MAX) => 255

I agree with @straight-shoota that I don't see a practical use case for different numerical types (other than Nil).