integer overflow in std.sort.sort due to incorrect lessThan implementation #8289
Description
I encountered an integer overflow in std.sort.sort on master (96ae451)
Example code (sort_test.zig)
const std = @import("std");
fn compareLeq(context: void, left: u8, right: u8) bool {
return left <= right; // This crashes when buffer.len >= 1024
// return true; // This also has the same behavior
}
test {
var buffer = try std.testing.allocator.alloc(u8, 1024);
defer std.testing.allocator.free(buffer);
for (buffer) |*b| b.* = 0;
// These work fine...
std.sort.sort(u8, buffer[0..1023], {}, comptime std.sort.asc(u8));
std.sort.sort(u8, buffer[0..1024], {}, comptime std.sort.asc(u8));
std.sort.sort(u8, buffer[0..1023], {}, comptime std.sort.desc(u8));
std.sort.sort(u8, buffer[0..1024], {}, comptime std.sort.desc(u8));
std.sort.sort(u8, buffer[0..1023], {}, compareLeq);
// ..but this crashes
std.sort.sort(u8, buffer[0..1024], {}, compareLeq);
}zig test results:
> zig version
0.8.0-dev.4206+96ae451
> uname -mo
x86_64 GNU/Linux
> zig test sort_test.zig
thread 25201 panic: integer overflow
/home/zbanks/zig/build/lib/zig/std/sort.zig:584:85: 0x21d64a in std.sort.sort (test)
mem.rotate(T, items[range.start..range.end], range.length() - count);
^
/tmp/sort_test.zig:22:18: 0x207ad1 in test "" (test)
std.sort.sort(usize, buffer[0..1024], {}, compareLeq);
^
/home/zbanks/zig/build/lib/zig/std/special/test_runner.zig:69:28: 0x258ca8 in std.special.main (test)
} else test_fn.func();
^
/home/zbanks/zig/build/lib/zig/std/start.zig:345:37: 0x21fd34 in std.start.posixCallMainAndExit (test)
const result = root.main() catch |err| {
^
/home/zbanks/zig/build/lib/zig/std/start.zig:163:5: 0x21fbd2 in std.start._start (test)
@call(.{ .modifier = .never_inline }, posixCallMainAndExit, .{});
^
error: the following test command crashed:
zig-cache/o/434532b9c0442450ef292055642d5b54/test /home/zbanks/zig/build/zig
Locals, from gdb:
>6 0x000000000024bd0b in std.sort.sort (items=...) at /home/zbanks/zig/build/lib/zig/std/sort.zig:584
584 mem.rotate(T, items[range.start..range.end], range.length() - count);
(gdb) info local
range = {start = 24, end = 24}
length = 24
A = {start = 0, end = 512}
last = 23
pull_index = 0
pull = {{from = 23, to = 0, count = 24, range = {start = 0, end = 1024}}, {from = 0, to = 0, count = 0, range = {start = 0, end = 0}}}
buffer1 = {start = 0, end = 24}
block_size = 22
buffer_size = 24
B = {start = 512, end = 1024}
count = 1
buffer2 = {start = 0, end = 0}
find_separately = false
index = 23
find = 24
start = 0
cache = {0 <repeats 256 times>, 12297829382473034410 <repeats 256 times>}
iterator = {size = 1024, power_of_two = 1024, numerator = 0, decimal = 1024, denominator = 256, decimal_step = 512, numerator_step = 0}
I encountered this on a list with unique (I think) elements -- but this is more concise example.