Commit `812557bfde`

Jay Petacat <jay@jayschwa.net>

2024-09-10 06:23:18

std: Restore conventional `compareFn` behavior for `binarySearch`

PR #20927 made some improvements to the `binarySearch` API, but one change I found surprising was the relationship between the left-hand and right-hand parameters of `compareFn` was inverted. This is different from how comparison functions typically behave, both in other parts of Zig (e.g. `std.math.order`) and in other languages (e.g. C's `bsearch`). Unless a strong reason can be identified and documented for doing otherwise, I think it'll be better to stick with convention. While writing this patch and changing things back to the way they were, the predicates of `lowerBound` and `upperBound` seemed to be the only areas that benefited from the inversion. I don't think that benefit is worth the cost, personally. Calling `Order.invert()` in the predicates accomplishes the same goal.

master

1 parent 7caa3d9

Changed files (5)

lib

compiler

aro

Preprocessor.zig

std

debug

@@ -271,7 +271,7 @@ fn clearBuffers(pp: *Preprocessor) void {
 pub fn expansionSlice(pp: *Preprocessor, tok: Tree.TokenIndex) []Source.Location {
     const S = struct {
         fn orderTokenIndex(context: Tree.TokenIndex, item: Tree.TokenIndex) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
     };

@@ -196,7 +196,7 @@ pub fn resolveAddressesDwarf(
             const table_addrs = slc.line_table.keys();
             line_table_i = std.sort.upperBound(u64, table_addrs, pc, struct {
                 fn order(context: u64, item: u64) std.math.Order {
-                    return std.math.order(item, context);
+                    return std.math.order(context, item);
                 }
             }.order);
         }

@@ -182,7 +182,7 @@ pub const CompileUnit = struct {
         pub fn findSource(slc: *const SrcLocCache, address: u64) !LineEntry {
             const index = std.sort.upperBound(u64, slc.line_table.keys(), address, struct {
                 fn order(context: u64, item: u64) std.math.Order {
-                    return std.math.order(item, context);
+                    return std.math.order(context, item);
                 }
             }.order);
             if (index == 0) return missing();

@@ -1624,12 +1624,12 @@ pub fn unwindFrameDwarf(
     } else {
         const index = std.sort.binarySearch(Dwarf.FrameDescriptionEntry, di.fde_list.items, context.pc, struct {
             pub fn compareFn(pc: usize, item: Dwarf.FrameDescriptionEntry) std.math.Order {
-                if (pc < item.pc_begin) return .gt;
+                if (pc < item.pc_begin) return .lt;
 
                 const range_end = item.pc_begin + item.pc_range;
                 if (pc < range_end) return .eq;
 
-                return .lt;
+                return .gt;
             }
         }.compareFn);

@@ -461,8 +461,8 @@ pub fn binarySearch(
         const mid = low + (high - low) / 2;
         switch (compareFn(context, items[mid])) {
             .eq => return mid,
-            .lt => low = mid + 1, // item too small
-            .gt => high = mid, // item too big
+            .gt => low = mid + 1,
+            .lt => high = mid,
         }
     }
     return null;
@@ -471,13 +471,13 @@ pub fn binarySearch(
 test binarySearch {
     const S = struct {
         fn orderU32(context: u32, item: u32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn orderI32(context: i32, item: i32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn orderLength(context: usize, item: []const u8) std.math.Order {
-            return std.math.order(item.len, context);
+            return std.math.order(context, item.len);
         }
     };
     const R = struct {
@@ -489,9 +489,9 @@ test binarySearch {
         }
 
         fn order(context: i32, item: @This()) std.math.Order {
-            if (item.e < context) {
+            if (context < item.b) {
                 return .lt;
-            } else if (item.b > context) {
+            } else if (context > item.e) {
                 return .gt;
             } else {
                 return .eq;
@@ -513,9 +513,8 @@ test binarySearch {
     try std.testing.expectEqual(2, binarySearch([]const u8, &[_][]const u8{ "", "abc", "1234", "vwxyz" }, @as(usize, 4), S.orderLength));
 }
 
-/// Returns the index of the first element in `items` returning `.eq` or `.gt`
-/// when given to `compareFn`.
-/// - Returns `items.len` if all elements return `.lt`.
+/// Returns the index of the first element in `items` that is greater than or equal to `context`,
+/// as determined by `compareFn`. If no such element exists, returns `items.len`.
 ///
 /// `items` must be sorted in ascending order with respect to `compareFn`:
 /// ```
@@ -540,7 +539,7 @@ pub fn lowerBound(
 ) usize {
     const S = struct {
         fn predicate(ctx: @TypeOf(context), item: T) bool {
-            return compareFn(ctx, item) == .lt;
+            return compareFn(ctx, item).invert() == .lt;
         }
     };
     return partitionPoint(T, items, context, S.predicate);
@@ -549,13 +548,13 @@ pub fn lowerBound(
 test lowerBound {
     const S = struct {
         fn compareU32(context: u32, item: u32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn compareI32(context: i32, item: i32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn compareF32(context: f32, item: f32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
     };
     const R = struct {
@@ -566,7 +565,7 @@ test lowerBound {
         }
 
         fn compareFn(context: i32, item: @This()) std.math.Order {
-            return std.math.order(item.val, context);
+            return std.math.order(context, item.val);
         }
     };
 
@@ -584,9 +583,8 @@ test lowerBound {
     try std.testing.expectEqual(2, lowerBound(R, &[_]R{ R.r(-100), R.r(-40), R.r(-10), R.r(30) }, @as(i32, -20), R.compareFn));
 }
 
-/// Returns the index of the first element in `items` returning `.gt`
-/// when given to `compareFn`.
-/// - Returns `items.len` if none of the elements return `.gt`.
+/// Returns the index of the first element in `items` that is greater than `context`, as determined
+/// by `compareFn`. If no such element exists, returns `items.len`.
 ///
 /// `items` must be sorted in ascending order with respect to `compareFn`:
 /// ```
@@ -611,7 +609,7 @@ pub fn upperBound(
 ) usize {
     const S = struct {
         fn predicate(ctx: @TypeOf(context), item: T) bool {
-            return compareFn(ctx, item) != .gt;
+            return compareFn(ctx, item).invert() != .gt;
         }
     };
     return partitionPoint(T, items, context, S.predicate);
@@ -620,13 +618,13 @@ pub fn upperBound(
 test upperBound {
     const S = struct {
         fn compareU32(context: u32, item: u32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn compareI32(context: i32, item: i32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn compareF32(context: f32, item: f32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
     };
     const R = struct {
@@ -637,7 +635,7 @@ test upperBound {
         }
 
         fn compareFn(context: i32, item: @This()) std.math.Order {
-            return std.math.order(item.val, context);
+            return std.math.order(context, item.val);
         }
     };
 
@@ -780,16 +778,16 @@ pub fn equalRange(
 test equalRange {
     const S = struct {
         fn orderU32(context: u32, item: u32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn orderI32(context: i32, item: i32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn orderF32(context: f32, item: f32) std.math.Order {
-            return std.math.order(item, context);
+            return std.math.order(context, item);
         }
         fn orderLength(context: usize, item: []const u8) std.math.Order {
-            return std.math.order(item.len, context);
+            return std.math.order(context, item.len);
         }
     };

Commit 812557bfde

Commit `812557bfde`