Julia: findnext() does not give BoundsErrors for small negative indices

[AndrewQuinn2020]

julia> versioninfo()
Julia Version 1.2.0
Commit c6da87ff4b (2019-08-20 00:03 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
Environment:
  JULIA_EDITOR = "C:\Users\Andre\AppData\Local\atom\app-1.40.1\atom.exe"  -a
  JULIA_NUM_THREADS = 4

This will make the most sense with an example. This bug is readily reproducible, AFAIK.

julia> findnext("Kitten", "Kitten", 1) # Normal operation.
1:6

julia> findnext("Kitten", "Kitten", 0) # Abnormal operation.
1:6

julia> findnext("Kitten", "Kitten", -1) # Abnormal operation.
1:6

julia> findnext("Kitten", "Kitten", -2) # Abnormal operation.
1:6

julia> findnext("Kitten", "Kitten", -3) # Abnormal operation.
1:6

julia> findnext("Kitten", "Kitten", -4) # Abnormal operation.
1:6

julia> findnext("Kitten", "Kitten", -5) # Normal operation.
ERROR: BoundsError: attempt to access 6-element Array{UInt8,1} at index [0]
Stacktrace:
 [1] getindex at .\array.jl:728 [inlined]
 [2] _nthbyte at .\strings\search.jl:148 [inlined]
 [3] _searchindex(::Array{UInt8,1}, ::Array{UInt8,1}, ::Int64) at .\strings\search.jl:185
 [4] _searchindex(::String, ::String, ::Int64) at .\strings\search.jl:153
 [5] _search(::String, ::String, ::Int64) at .\strings\search.jl:220
 [6] findnext(::String, ::String, ::Int64) at .\strings\search.jl:256
 [7] top-level scope at none:0

In other wrods, findnext allows some, but not all, non-positive indexes to work.

Behavior seems dependent on string length, or maybe just differing string contents, to work:

julia> s
"Supercalifragilisticexpialidocious"

julia> length(s)
34

julia> findnext(s, s, -10)
1:34

julia> findnext(s, s, -15)
1:34

julia> findnext(s, s, -16)
ERROR: BoundsError: attempt to access 34-element Array{UInt8,1} at index [-16]
Stacktrace:
 [1] getindex at .\array.jl:728 [inlined]
 [2] _nthbyte at .\strings\search.jl:148 [inlined]
 [3] _searchindex(::Array{UInt8,1}, ::Array{UInt8,1}, ::Int64) at .\strings\search.jl:189
 [4] _searchindex(::String, ::String, ::Int64) at .\strings\search.jl:153
 [5] _search(::String, ::String, ::Int64) at .\strings\search.jl:220
 [6] findnext(::String, ::String, ::Int64) at .\strings\search.jl:256
 [7] top-level scope at none:0

julia> # Seems like it's tied to the length of the string in question; 16 is almost half of 34.

julia> # Possibly an issue with divrem(x,y) vs. fldmod(x,y) in the source code?

---

I'll point out that this doesn't happen in reverse, with large positive numbers being entered into findprev.

julia> s
"Supercalifragilisticexpialidocious"

julia> findprev(s, s, 100)
1:34

julia> findprev(s, s, typemax(Int64))
1:34

julia> typemax(Int64)
9223372036854775807

The behavior gets even stranger when we consider more edge cases. For example, findnext returns nothing when given indices larger than the maximal byte index of the string, but findprev throws a BoundsError when given indices smaller than the minimal byte index of the string. Curious.

julia> findnext(s, s, typemax(Int64)) # Returns Nothing, because the search failed.

julia> findprev(s, s, typemin(Int64))
ERROR: BoundsError: attempt to access "Supercalifragilisticexpialidocious"
  at index [-9223372036854775808]
Stacktrace:
 [1] _nextind_str(::String, ::Int64) at .\strings\string.jl:140
 [2] nextind at .\strings\string.jl:134 [inlined]
 [3] _rsearchindex(::String, ::String, ::Int64) at .\strings\search.jl:321
 [4] _rsearch(::String, ::String, ::Int64) at .\strings\search.jl:396
 [5] findprev(::String, ::String, ::Int64) at .\strings\search.jl:429
 [6] top-level scope at none:0

[AndrewQuinn2020]

I'm willing to bug hunt in the code for this once I understand what you guys want for the language, although I'll need to wait until at least this weekend to do so. :)

[StefanKarpinski]

@rfourquet, findnext et al are your adoptive children, would you be willing to have a look?

[rfourquet]

Haha, I didn't know that! :sweat_smile:
But I don't know the implementation of this method and am not sure when I will have time to look at this. Anyone feel free to take care of this child!