odin-lang / Odin

Odin Programming Language
https://odin-lang.org
BSD 3-Clause "New" or "Revised" License
6.95k stars 615 forks source link

Bug in binary_search_by implementation #3007

Closed xtactis closed 11 months ago

xtactis commented 11 months ago

Context

I believe there is a bug in the implementation of slice.binary_search_by. https://github.com/odin-lang/Odin/blob/31b1aef44e1b0178f10f5faa62ceedddda56667b/core/slice/slice.odin#L173-L174

        Odin: dev-2023-12:4aa8834d
        OS:   Ubuntu 22.04.2 LTS, Linux 5.15.90.1-microsoft-standard-WSL2
        CPU:  AMD Ryzen 9 7940HS w/ Radeon 780M Graphics
        RAM:  7550 MiB

Expected Behavior

I should be able to search arbitrary types, since I'm the one specifying the comparator function.

Current Behavior

Doesn't compile because of the requirement that the underlying type is intrinsics.type_is_ordered.

Failure Information (for bugs)

Error: 'where' clause evaluated to false:
        intrinsics.type_is_ordered(T)
        where intrinsics.type_is_ordered(T) #no_bounds_check
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~^

        With the following definitions:
                T :: []int;
                A :: [][]int;

Steps to Reproduce

  1. Try to run or build the following minimal code snippet
    package BS_Bug
    import "core:slice"
    main :: proc() {
    array_of_arrays := [][]int{{1, 2, 3}, {100, 200, 300}, {301, 202, 103}}
    _, _ := slice.binary_search_by(array_of_arrays, []int{0, 200, 0}, proc(a, b: []int) -> slice.Ordering {
        return slice.cmp(a[1], b[1])
    })
    }
laytan commented 11 months ago

Yeah seems like an oversight. I am sure a PR removing the where clause would be accepted ;)