BoundsError occurs randomly

[xiorcale]

I was trying the package with this simple, "dummy" script:

using BSDiff

old = rand(UInt8, 60000)
new = deepcopy(old)
new[1:30000] = rand(UInt8, 30000)

patch = IOBuffer()
bsdiff(IOBuffer(old), IOBuffer(new), patch)
patch = take!(patch)

println(length(patch))

res = IOBuffer()
bspatch(IOBuffer(old), res, IOBuffer(patch))

take!(res)

I experienced a BoundsError from time to time (the bigger is the size of old / new the more frequent the error will occur). Here is the stacktrace:

ERROR: LoadError: BoundsError: attempt to access 60000-element Array{Int64,1} at index [60001]
Stacktrace:
 [1] getindex at ./array.jl:809 [inlined]
 [2] getindex at /home/xiorcale/.julia/packages/SuffixArrays/sKeKJ/src/sais.jl:32 [inlined]
 [3] iterate at ./abstractarray.jl:986 [inlined]
 [4] _zip_iterate_some at ./iterators.jl:352 [inlined]
 [5] _zip_iterate_all at ./iterators.jl:344 [inlined]
 [6] iterate at ./iterators.jl:335 [inlined]
 [7] == at ./abstractarray.jl:1869 [inlined]
 [8] LMSsort(::SuffixArrays.IntVector, ::Array{Int32,1}, ::SuffixArrays.IntVector, ::SuffixArrays.IntVector, ::Int64, ::Int64) at /home/xiorcale/.julia/packages/SuffixArrays/sKeKJ/src/sais.jl:239
 [9] sais(::SuffixArrays.IntVector, ::Array{Int32,1}, ::Int64, ::Int64, ::Int64, ::Bool) at /home/xiorcale/.julia/packages/SuffixArrays/sKeKJ/src/sais.jl:134
 [10] sais(::Array{UInt8,1}, ::Array{Int32,1}, ::Int64, ::Int64, ::Int64, ::Bool) at /home/xiorcale/.julia/packages/SuffixArrays/sKeKJ/src/sais.jl:160
 [11] suffixsort(::Array{UInt8,1}, ::Int64) at /home/xiorcale/.julia/packages/SuffixArrays/sKeKJ/src/SuffixArrays.jl:30
 [12] generate_index at /home/xiorcale/.julia/packages/BSDiff/6S88g/src/BSDiff.jl:205 [inlined]
 [13] data_and_index at /home/xiorcale/.julia/packages/BSDiff/6S88g/src/BSDiff.jl:182 [inlined]
 [14] bsdiff(::Base.GenericIOBuffer{Array{UInt8,1}}, ::Base.GenericIOBuffer{Array{UInt8,1}}, ::Base.GenericIOBuffer{Array{UInt8,1}}; format::Symbol) at /home/xiorcale/.julia/packages/BSDiff/6S88g/src/BSDiff.jl:90
 [15] bsdiff(::Base.GenericIOBuffer{Array{UInt8,1}}, ::Base.GenericIOBuffer{Array{UInt8,1}}, ::Base.GenericIOBuffer{Array{UInt8,1}}) at /home/xiorcale/.julia/packages/BSDiff/6S88g/src/BSDiff.jl:89
 [16] top-level scope at /home/xiorcale/Documents/diff.jl:8
 [17] include(::String) at ./client.jl:457
 [18] top-level scope at REPL[6]:1
 [19] run_repl(::REPL.AbstractREPL, ::Any) at /builddir/build/BUILD/julia/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:288
in expression starting at /home/xiorcale/Documents/diff.jl:8

I suspect an error linked to the values of the input data (since they are random, which would explain why the error does not occur every time). Any idea on what could cause it?

[StefanKarpinski]

This seems to be a bug in the SuffixArray suffixsort implementation. cc @quinnj

[xiorcale]

Yes, I saw this merged request: #17 which claims to solve the problem, but I guess there is something else causing it too.