ziglang
std: Avoid overflowing in the midpoint calculation in upperBound
The line that calculates the midpoint in the upperBound function didn't take into account overflows from large arrays like in other binary search functions.
Is it possible to add a regression test that would ensure this doesn't break again?
How should I write the unit test? Triggering an overflow requires the left and right indices add up to greater than max of usize. Allocating a 2 GB array to test it seems feasible for a 32-bit system, but I'm not sure if you can allocate 2^63 bytes on most 64-bit systems.
There's upperBound unit tests a little further down in the code, you should be able to add your test there. No need to actually allocate that much memory.
No need to actually allocate that much memory.
Unless I'm missing something, there is; the relevant thing is items.len.
I suppose one way to get around that would be to split upperBound into two functions:
pub fn upperBound(
comptime T: type,
key: anytype,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: @TypeOf(key), rhs: T) bool,
) usize {
return upperBound(usize, T, key, items, context, lessThan);
}
fn upperBoundImpl(
comptime IndexType: type,
comptime T: type,
key: anytype,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: @TypeOf(key), rhs: T) bool,
) usize {
var left: IndexType = 0;
var right: IndexType = @intCast(items.len);
while (left < right) {
const mid = left + (right - left) / 2;
if (!lessThan(context, key, items[mid])) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
so then upperBoundImpl could be tested with a smaller IndexType. Not sure if there's a use-case for this outside of testing for the overflow, though.
