Commit e03026507f

Alex Kladov <aleksey.kladov@gmail.com>
2024-06-20 21:38:54
std: fuzz test sort stability (#20284)
Stability of std sort was undertested before this change. Add a fuzz test for more confidence. Specifically, we used to have a single example test that used an array of eight elements. That ends up exercising only a tiny fraction of sorting logic, as it hits a hard-coded sorting network due to small size.
master
1 parent 5afd774
Changed files (1)
lib
std
sort.zig
lib/std/sort.zig
@@ -222,6 +222,35 @@ test "stable sort" {
     }
 }
 
+test "stable sort fuzz testing" {
+    var prng = std.Random.DefaultPrng.init(0x12345678);
+    const random = prng.random();
+    const test_case_count = 10;
+
+    for (0..test_case_count) |_| {
+        const array_size = random.intRangeLessThan(usize, 0, 1000);
+        const array = try testing.allocator.alloc(IdAndValue, array_size);
+        defer testing.allocator.free(array);
+        // Value is a small random numbers to create collisions.
+        // Id is a  reverse index to make sure sorting function only uses provided `lessThan`.
+        for (array, 0..) |*item, index| {
+            item.* = .{
+                .value = random.intRangeLessThan(i32, 0, 100),
+                .id = array_size - index,
+            };
+        }
+        block(IdAndValue, array, {}, IdAndValue.lessThan);
+        if (array_size > 0) {
+            for (array[0 .. array_size - 1], array[1..]) |x, y| {
+                try testing.expect(x.value <= y.value);
+                if (x.value == y.value) {
+                    try testing.expect(x.id > y.id);
+                }
+            }
+        }
+    }
+}
+
 test "sort" {
     const u8cases = [_][]const []const u8{
         &[_][]const u8{
@@ -384,8 +413,7 @@ test "sort fuzz testing" {
     const test_case_count = 10;
 
     inline for (sort_funcs) |sortFn| {
-        var i: usize = 0;
-        while (i < test_case_count) : (i += 1) {
+        for (0..test_case_count) |_| {
             const array_size = random.intRangeLessThan(usize, 0, 1000);
             const array = try testing.allocator.alloc(i32, array_size);
             defer testing.allocator.free(array);