`dbscan` does not work using `StaticArrays < 1.4.6`

[fhagemann]

I spotted this using Clustering, but the underlying is NearestNeighbors using setindex on a StaticArray with index of type UInt16.

MWE:

# running in julia-1.10
import Pkg
Pkg.add("Clustering")
Pkg.add("NearestNeighbors")
Pkg.add(Pkg.PackageSpec(name = "StaticArrays", version = "1.0.0")) # every version until "1.4.5"

using Clustering
Clustering.dbscan([ 1 1 1 ; 1 2 3. ], 1, leafsize = 1)

MethodError: no method matching setindex(::StaticArrays.SVector{3, Float64}, ::Float64, ::UInt16)
The function `setindex` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  setindex(::StaticArrays.StaticArray, ::Any, ::Int64)
   @ StaticArrays ~/.julia/packages/StaticArrays/WNOVH/src/deque.jl:185
  setindex(::StaticArrays.StaticArray, ::Any, ::Int64...)
   @ StaticArrays ~/.julia/packages/StaticArrays/WNOVH/src/deque.jl:198
  setindex(::CartesianIndex, ::Any, ::Any)
   @ Base multidimensional.jl:106
  ...

Stacktrace:
 [1] inrange_kernel!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, index::Int64, point::SubArray{Float64, 1, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, false}, r::Int64, idx_in_ball::Vector{Int64}, hyper_rec::NearestNeighbors.HyperRectangle{StaticArrays.SVector{3, Float64}}, min_dist::Float64, max_dist_contribs::StaticArrays.SVector{3, Float64}, max_dist::Float64)
   @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/kd_tree.jl:254
 [2] _inrange(tree::NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, point::SubArray{Float64, 1, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, false}, radius::Int64, idx_in_ball::Vector{Int64})
   @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/kd_tree.jl:207
 [3] inrange_point!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, point::SubArray{Float64, 1, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, false}, radius::Int64, sortres::Bool, idx::Vector{Int64})
   @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:34
 [4] inrange!(idxs::Vector{Int64}, tree::NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, point::SubArray{Float64, 1, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, false}, radius::Int64, sortres::Bool)
   @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:64
 [5] inrange (repeats 2 times)
   @ ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:69 [inlined]
 [6] _dbscan_region_query!(neighbors::Vector{Int64}, nntree_and_points::Tuple{NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}}, point::Int64, radius::Int64)
   @ Clustering ~/.julia/packages/Clustering/M6mjF/src/dbscan.jl:185
 [7] _dbscan(data::Tuple{NearestNeighbors.KDTree{StaticArrays.SVector{3, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{3, Float64}}, LinearAlgebra.Adjoint{Float64, Matrix{Float64}}}, num_points::Int64, radius::Int64, min_neighbors::Int64, min_cluster_size::Int64)
   @ Clustering ~/.julia/packages/Clustering/M6mjF/src/dbscan.jl:141
 [8] dbscan(points::LinearAlgebra.Adjoint{Float64, Matrix{Float64}}, radius::Int64; metric::Distances.Euclidean, min_neighbors::Int64, min_cluster_size::Int64, nntree_kwargs::@Kwargs{leafsize::Int64})
   @ Clustering ~/.julia/packages/Clustering/M6mjF/src/dbscan.jl:113
 [9] top-level scope
   @ REPL[3]:1

This behavior seems to have been introduced in #166, when going from split_dim::Int to split_dim::Int16 in NearestNeighbors ≥ 0.4.14

NearestNeighbors allows for StaticArrays versions down to 0.9.0, even though it should only allow for StaticArrays ≥ 0.14.6 since /NearestNeighbors@0.4.14.

[KristofferC]

Hm, even when we fix it here now, if there is an environment that requires an older StaticArray the resolver will just pick an older NearestNeighbors version that claims to be compatible with it. So fixing it here doesn't really help anything, almost feels like it requires rewriting the existing compat bounds .

[fhagemann]

I see..

So, that would mean modifying the Compat.toml in the General Julia registry?
I would argue that it might make sense to default back to NearestNeighbor@0.4.13 when using old StaticArrays versions, because everything 0.4.14 and newer just simply either won't compile or won't 100% work.

[KristofferC]

How about we just convert the index that we index with to Int? Then we should work with older StaticArrays and the resolver should never really decide to use an older NearestNeighbors without this fix?

[fhagemann]

This sounds good to me!

[fhagemann]

Even though, there seem to be more issues than the one I reported, e.g.

# run on julia-1.10
import Pkg
Pkg.add("NearestNeighbors")
Pkg.add(Pkg.PackageSpec(name = "StaticArrays", version = "0.9.0"))

using NearestNeighbors

ERROR: The following 1 direct dependency failed to precompile:

NearestNeighbors 

Failed to precompile NearestNeighbors [b8a86587-4115-5ab1-83bc-aa920d37bbce] to "/home/hagemann/.julia/compiled/v1.10/NearestNeighbors/jl_3xKsjR".
ERROR: LoadError: No precise constructor for StaticArrays.SVector{2, Float64} found. Length of input was 1.
Stacktrace:
  [1] error(s::String)
    @ Base ./error.jl:35
  [2] StaticArrays.SVector{2, Float64}(x::Tuple{Tuple{Tuple{Tuple{Base.Generator{Base.OneTo{Int64}, NearestNeighbors.var"#24#25"{Float64, Distances.Euclidean, NearestNeighbors.HyperRectangle{StaticArrays.SVector{2, Float64}}, Vector{Float64}, Nothing}}}}}})
    @ StaticArrays ~/.julia/packages/StaticArrays/Rznwo/src/convert.jl:1
  [3] StaticArray
    @ ~/.julia/packages/StaticArrays/Rznwo/src/convert.jl:3 [inlined]
  [4] StaticArrays.SVector{2, Float64}(x::Tuple{Tuple{Base.Generator{Base.OneTo{Int64}, NearestNeighbors.var"#24#25"{Float64, Distances.Euclidean, NearestNeighbors.HyperRectangle{StaticArrays.SVector{2, Float64}}, Vector{Float64}, Nothing}}}})
    @ StaticArrays ~/.julia/packages/StaticArrays/Rznwo/src/convert.jl:3
  [5] StaticArray (repeats 2 times)
    @ ~/.julia/packages/StaticArrays/Rznwo/src/convert.jl:3 [inlined]
  [6] get_max_distance_contributions(m::Distances.Euclidean, rec::NearestNeighbors.HyperRectangle{StaticArrays.SVector{2, Float64}}, point::Vector{Float64})
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/hyperrectangles.jl:60
  [7] _inrange(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{2, Float64}}, point::Vector{Float64}, radius::Float64, idx_in_ball::Vector{Int64})
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/kd_tree.jl:205
  [8] inrange_point!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{2, Float64}}, point::Vector{Float64}, radius::Float64, sortres::Bool, idx::Vector{Int64})
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:34
  [9] inrange!(idxs::Vector{Int64}, tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{2, Float64}}, point::Vector{Float64}, radius::Float64, sortres::Bool)
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:64
 [10] inrange(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{2, Float64}}, point::Vector{Float64}, radius::Float64, sortres::Bool)
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:69
 [11] inrange(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64, StaticArrays.SVector{2, Float64}}, point::Vector{Float64}, radius::Float64)
    @ NearestNeighbors ~/.julia/packages/NearestNeighbors/3NRL1/src/inrange.jl:69
 [12] top-level scope
    @ ~/.julia/packages/NearestNeighbors/3NRL1/src/NearestNeighbors.jl:67
 [13] include
    @ ./Base.jl:495 [inlined]
 [14] include_package_for_output(pkg::Base.PkgId, input::String, depot_path::Vector{String}, dl_load_path::Vector{String}, load_path::Vector{String}, concrete_deps::Vector{Pair{Base.PkgId, UInt128}}, source::Nothing)
    @ Base ./loading.jl:2292
 [15] top-level scope
    @ stdin:4
in expression starting at /home/hagemann/.julia/packages/NearestNeighbors/3NRL1/src/NearestNeighbors.jl:1
in expression starting at stdin:

--> converting back to V (which can be StaticVector) in this line:

NearestNeighbors.jl/src/hyperrectangles.jl

Line 60 in 0d814ad

return V(

This was only fixed in StaticArrays@0.12.4 with PR JuliaArrays/StaticArrays.jl#792

[fhagemann]

If the Compat.toml in the General registry were to be updated, I think this would do the trick:
https://github.com/JuliaRegistries/General/blob/master/N/NearestNeighbors/Compat.toml

["0 - 0.4.3"]
Distances = "0.6 - 0.8"
StaticArrays = "0.7 - 0.12"
julia = ["0.7", "1"]

["0.4.14 - 0"]
julia = "1.6.0 - 1"
StaticArrays = "1.4.6"

["0.4.21 - 0"]
Distances = "0.10.12 - 0.10"

["0.4.4"]
Distances = "0.8.1 - 0.8"

["0.4.4 - 0.4.13"]
julia = "1"

["0.4.4 - 0.4.7"]
StaticArrays = "0.9 - 0.12"

["0.4.5 - 0.4.6"]
Distances = "0.9"

["0.4.7 - 0.4.20"]
Distances = "0.9 - 0.10"

["0.4.8 - 0.4.13"]
StaticArrays = ["0.9 - 0.12", "1"]