Fixes constructor of SubString from SubString #22511

bkamins · 2017-06-24T18:27:21Z

PR following https://discourse.julialang.org/t/do-not-allow-substring-to-grow/4438

nalimilan · 2017-06-24T20:51:45Z

I think this should rather be an error, just like when trying to index a string with an invalid index range. See how getindex(s::String, r::UnitRange{Int}) works. Also, the check should happen in the inner constructor so that it cannot be bypassed, except by using an explicit @inbounds (this will require the check to be annotated with @boundscheck).

davidanthoff · 2017-06-24T23:11:17Z

I agree with @nalimilan, I think this should throw an error.

bkamins · 2017-06-25T06:13:03Z

Before fixing this I have one question. Do you want also:

julia> x=""
julia> SubString(x, 5, 10)

to throw an error except when annotated with @inbounds?

I want to make sure as I believe that in the initial design of SubString it was intentional to allow this.

nalimilan · 2017-06-25T08:36:58Z

I would say yes, but where did you read that this was supposed to work?

bkamins · 2017-06-25T09:16:22Z

@nalimilan Tests imply that. Everything starting from the line:
https://github.com/JuliaLang/julia/blob/master/test/strings/types.jl#L32
to the line:
https://github.com/JuliaLang/julia/blob/master/test/strings/types.jl#L45
should throw an error if we change this.
Additionally if we want to be consistent the following should be also fixed:

julia> x="∀"
"∀"

julia> x[2:3]
ERROR: UnicodeError: invalid character index
Stacktrace:
 [1] getindex(::String, ::UnitRange{Int64}) at .\strings\string.jl:239

julia> SubString(x, 2, 3)
""

In general I would recommend to have SubString work exactly like function getindex(s::String, r::UnitRange{Int}) except that it does not perform a copy. If this is what is what we agree on I can go on and implement it.

The only question is about @inbounds. Because now @inbounds in getindex does not disable bounds checking - I feel that it would be safer to always check bounds in SubString, as with Unicode it is very error prone to assume that you guarantee that you give proper bounds.
Finally I would add documentation to SubString.

davidanthoff · 2017-06-25T15:44:47Z

I think that all makes sense. You could do a git blame and figure out who wrote these tests and ping that person, maybe there was a deeper rational for it.

bkamins · 2017-06-25T16:17:47Z

I have pushed an initial proposal how SubString could be improved.
@ScottPJones could you please review the assumptions how SubString should work, as it changes the initial design of the functionality.

nalimilan · 2017-06-25T17:34:04Z

Actually @ScottPJones didn't write these tests, he split tests into several files. These tests were added in #7145, a PR which was about introducing a more efficient implementation of length rather than about changing its behavior. So that doesn't say anything about the justification for that behavior.

@StefanKarpinski and @stevengj would probably know better, but copying the behavior of getindex sounds like a good idea to me. Regarding @inbounds, it's fine not to implement it for now, but I don't buy the argument that it shouldn't be added because Unicode is complex: if people use @inbounds, they explicitly state that they take care of using valid indices.

nalimilan · 2017-06-25T17:40:36Z

base/strings/types.jl

+        j > endof(s) && throw(BoundsError(s, j))
+
+        if !isvalid(s,i)
+            throw(ArgumentError("invalid SubString index i"))


It would make sense to print "$i" rather than just "i".

I meant symbol i as it is a name of the first argument. Invalid second argument j is allowed (like in getinex).

After rethinking I have hanget it to i=$i.

tkelman · 2017-06-25T23:53:54Z

base/strings/types.jl

@@ -19,10 +19,10 @@ struct SubString{T<:AbstractString} <: AbstractString
    function SubString{T}(s::T, i::Int, j::Int) where T<:AbstractString
        i > j && return new(s, 0, 0) # allow i > j as it is consistent with getindex
        i < 1 && throw(BoundsError(s, i))
-        j > endof(s) && throw(BoundsError(s, j))
+        j > s.len && throw(BoundsError(s, j))


it's not guaranteed that all AbstractString subtypes will have a .len field - that's even going to be removed from String soon

@tkelman Changed to sizeof (I understand it will stay).

sizeof isn't correct here. For example, when indexing "café":

julia> sizeof("café") 5 julia> endof("café") 4

nalimilan · 2017-06-26T08:40:17Z

base/strings/types.jl

@@ -42,7 +42,7 @@ SubString(s::AbstractString, r::UnitRange{<:Integer}) = SubString(s, Int(first(r
 function SubString(s::SubString, i::Int, j::Int)
    i > j && SubString(s.string, 1, 0) # allow i > j as it is consistent with getindex
    i < 1 && throw(BoundsError(s, i))
-    j > endof(s) && throw(BoundsError(s, j))
+    j >= nextind(s, endof(s)) && throw(BoundsError(s, j))


Won't this always return endof(s) + 1? Why is this needed?

nalimilan · 2017-06-26T08:41:24Z

base/strings/types.jl

@@ -4,32 +4,47 @@

 ## substrings reference original strings ##

+"""
+    SubString(s::AbstractString, i::Integer, j::Integer)
+    SubString(s::AbstractString, r::UnitRange{Integer})


<:Integer

nalimilan · 2017-06-26T08:42:02Z

base/strings/types.jl

@@ -4,32 +4,47 @@

 ## substrings reference original strings ##

+"""
+    SubString(s::AbstractString, i::Integer, j::Integer)


j::Integer=endof(s).

nalimilan · 2017-06-26T08:42:34Z

base/strings/types.jl

+function SubString(s::SubString, i::Int, j::Int)
+    i > j && SubString(s.string, 1, 0) # allow i > j as it is consistent with getindex
+    i < 1 && throw(BoundsError(s, i))
+    j > sizeof(s) && throw(BoundsError(s, j))


nalimilan · 2017-06-26T08:43:37Z

test/strings/types.jl

@@ -110,8 +125,6 @@ let s="lorem ipsum",
               SubString(s,1,6)=>"lorem ",
               SubString(s,1,0)=>"",
               SubString(s,2,4)=>"ore",
-               SubString(s,2,16)=>"orem ipsum",


Maybe keep these examples, but with valid indices that still give the expected result?

bkamins · 2017-06-26T15:08:41Z

@nalimilan Thank you for the code review. I will wait with fixing it till #22548 is decided, as apart from obvious corrections your comments relate to the fact that I want to make SubString work like String with getindex.

Eg. currently:

julia> x="café"
"café"

julia> x[1:5]
"café"

goes through without error and that is why I have used sizeof.

And in general for me having consistent behavior of indexing for any AbstractString.

bkamins · 2017-06-26T22:09:34Z

Now SubString is defined following #22548.

nalimilan

I have a few comments. Looks like you'll have to dig into the bootstrap process to fix the CI failures. That's a relatively tedious work since it's hard to find out where the failures come from. Here it seems to be in the string interpolation code. You'll probably have to review all places using SubString and check for invalid indices.

nalimilan · 2017-06-27T07:53:22Z

base/strings/types.jl

+        i > j && return new(s, 0, 0) # allow i > j as it is consistent with getindex
+        isvalid(s, i) || throw(BoundsError(s, i))
+        isvalid(s, j) || throw(BoundsError(s, j))
+        o = i-1


o isn't really useful in the new code.

nalimilan · 2017-06-27T07:54:45Z

base/strings/types.jl

+SubString(s::AbstractString, r::UnitRange{<:Integer}) = SubString(s, first(r), last(r))
+
+function SubString(s::SubString, i::Int, j::Int)
+    i > j && SubString(s.string, 1, 0) # allow i > j as it is consistent with getindex


You don't need to check this here, as the inner constructor will do the same via s.offset+i > s.offset+j.

This is required as we allow any i>j (not necessarily valid) and return empty SubString then. This is required for consistency with getindex for String.

What I meant is that you call the inner constructor below, which already checks the indices, so this is redundant (just try without it).

The following test (which should pass) fails if I remove this line:
@test SubString(SubString("123", 1, 2), -10, -20) == ""
But there was an error as the line missed return before SubString so thank you for a detailed review 😄.

nalimilan · 2017-06-27T07:56:24Z

base/strings/types.jl

+
+function SubString(s::SubString, i::Int, j::Int)
+    i > j && SubString(s.string, 1, 0) # allow i > j as it is consistent with getindex
+    isvalid(s, i) || throw(BoundsError(s, i))


isvalid is relatively expensive, and will be checked by the inner constructor too. So better drop it in favor of a less costly check that i and j are within the bounds of the sub string. Then you can delegate to the inner constructor the question of whether they are also valid for the underlying string.

Yes, but I have to retain earlier i > j check, as SubString(SubString("fsfsdf", 1, 2), -10, -20) should go through and return empty substring.

nalimilan · 2017-06-27T07:57:56Z

test/strings/types.jl

-ss=SubString(str,1,length(str)) #match source string
+ss=SubString(str,1,endof(str)) #match source string
+@test length(ss)==length(str)
+ss=SubString(str,1:length(str)) # works as str is all ASCII


Just remove this test, it's not valid to index with length(str), and we don't really care that it works for ASCII strings.

nalimilan · 2017-06-27T07:58:17Z

test/strings/types.jl

 @test length(ss)==length(str)

 ss=SubString(str,1,0)    #empty SubString
 @test length(ss)==0
-


Keep blank line for consistency.

nalimilan · 2017-06-27T07:58:55Z

test/strings/types.jl

 @test length(ss)==0

-ss=SubString(str,10,16)  #end indexed beyond source string length
-@test length(ss)==3
+str = "∀"


No need to store the string in str, it's clearer to repeat it (especially since you change the contents of str). Also, it would be useful to add a short comment explaining what is tested to new tests.

nalimilan · 2017-06-27T08:02:14Z

test/strings/types.jl

+    @test_throws BoundsError SubString(str, 4, idx) == str[4:idx]
+end
+
+@test_throws BoundsError SubString(str,14,20)  #start indexed beyond source string length


"start indexed" -> "start index". Same below.

nalimilan · 2017-06-27T08:03:58Z

test/strings/types.jl

@@ -72,20 +98,23 @@ b = IOBuffer()
 write(b, u)
 @test String(take!(b)) == ""

-str = "føøbar"
-u = SubString(str, 10, 10)


I'd rather keep this test, just changing the indices. It's not clear what this tested, but it must have triggered a bug in a corner case.

This comment still seems to apply.

The test is retained but moved to line 95.

nalimilan · 2017-06-27T08:05:34Z

test/strings/types.jl

+    @test SubString(u, 2:idx) == u[2:idx]
+end
+@test_throws BoundsError SubString(u, 1, 10)
+@test_throws BoundsError SubString(u, 1:10)


Also test with start index out of bounds (both positive and negative).

Done below.

nalimilan · 2017-06-27T08:07:02Z

test/strings/types.jl

+    for i in -1:length(s)+2
+        if isvalid(s, i)
+            ss=SubString(s,1,i)
+            @test isvalid(ss,i)==isvalid(s,i)


==isvalid(s,i) is redundant since that's the condition. Also check that a BoundsError is raised when !isvalid(s,i).

bkamins · 2017-07-02T05:57:18Z

@nalimilan included your comments and working through bootstrap.

tkelman · 2017-07-02T06:21:48Z

test/strings/types.jl

 @test length(ss)==0

-ss=SubString(str,10,16)  #end indexed beyond source string length
-@test length(ss)==3
+# tests for SubString of as single multibyte `Char` string


of a single

tkelman · 2017-07-02T06:25:02Z

test/strings/types.jl

+    for i in -1:length(s)+2
+        if isvalid(s, i)
+            ss=SubString(s,1,i)
+            # make sure isvalid give equivalent resutls for SubString and String


gives equivalent results

bkamins · 2017-07-02T09:29:21Z

Fixed typos. Seems that some errors in Documenter.jl have to be fixed before this one is merged.

nalimilan · 2017-07-02T10:07:01Z

base/strings/types.jl

-            o = i-1
-            new(s, o, max(0, j-o))
-        end
+        i > j && return new(s, 0, 0) # allow i > j as it is consistent with getindex


You could continue to return new(s, i-1, 0) unless you've found a reason not to. I don't know what was the original justification for this behavior.

nalimilan · 2017-07-02T10:11:59Z

test/strings/types.jl

-@test length(ss)==0
+# tests for SubString of more than one multibyte `Char` string
+# we are consistent with `getindex` for `String`
+for idx in 0:1


Could also include idx = 4 here rather than in a separate line.

nalimilan · 2017-07-02T10:13:53Z

test/strings/types.jl

+
+@test SubString("∀∀", 4, 4) == "∀∀"[4:4]
+
+for idx in 5:8


Would be nice to have a comment explaining what is tested here. Same below, where some lines are commented and not others (a global comment for multiple lines is fine).

nalimilan · 2017-07-02T10:14:30Z

test/strings/types.jl

+    @test_throws BoundsError SubString("∀∀", 4, idx)
+end
+
+@test_throws BoundsError SubString(str,14,20)  #start indexing beyond source string length


It's weird to reuse str here after tests on a different string. Maybe put these tests above those on "∀"?

nalimilan · 2017-07-02T10:15:22Z

test/strings/types.jl

+
+@test_throws BoundsError SubString(str,2:4)
+
+str2=""


Would be clearer to get rid of str2 and use "" everywhere.

bkamins · 2017-09-20T16:06:05Z

Merge conflicts were introduced by #22572 - I will resolve them.

bkamins · 2017-09-21T22:13:09Z

I would like to ask for a merge or discard this PR before I finish implementation of #23765 as it will be using SubString.

nalimilan

Sorry, there are two details I hadn't seen (or were introduced in the rebase).

@StefanKarpinski @stevengj Good to merge after this?

nalimilan · 2017-09-22T08:29:09Z

base/regex.jl

    cap = Union{Void,SubString{String}}[
-            ovec[2i+1] == PCRE.UNSET ? nothing : SubString(str, ovec[2i+1]+1, ovec[2i+2]) for i=1:n ]
+    ovec[2i+1] == PCRE.UNSET ? nothing : SubString(str, ovec[2i+1]+1,


Indentation should be kept as this is inside an array comprehension.

nalimilan · 2017-09-22T08:29:42Z

base/strings/types.jl

+    SubString(s::AbstractString, i::Integer, j::Integer=endof(s))
+    SubString(s::AbstractString, r::UnitRange{<:Integer})
+
+Like [`getindex`](@ref), but returns a view into the parent AbstractString `s`


Missing backquotes around AbstractString, or better say "string".

bkamins · 2017-09-22T11:46:44Z

@nalimilan Thank you for the review as the rebase was not very simple.

nalimilan · 2017-09-22T11:53:02Z

base/regex.jl

-    ovec[2i+1] == PCRE.UNSET ? nothing : SubString(str, ovec[2i+1]+1,
-                                                   prevind(str, ovec[2i+2]+1)) for i=1:n ]
+            ovec[2i+1] == PCRE.UNSET ? nothing : SubString(str, ovec[2i+1]+1,
+            prevind(str, ovec[2i+2]+1)) for i=1:n ]


This one needs to be aligned with str. Or maybe better break after : or ?.

I hope now it is OK (I thought I have seen the layout I have used earlier somewhere in the code base).

bkamins · 2017-09-23T11:20:14Z

CI failures seem to be unrelated

bkamins · 2017-09-29T10:45:04Z

I have performed another rebase of conflicts introduced in the meantime.
Is it good to merge?

KristofferC · 2017-10-01T12:01:07Z

Does this need a NEWS entry?

bkamins · 2017-10-01T12:25:21Z

@KristofferC I have proposed a news entry.

nalimilan · 2017-10-01T13:08:56Z

NEWS.md

@@ -238,6 +238,9 @@ Library improvements

  * The functions `strip`, `lstrip` and `rstrip` now return `SubString` ([#22496]).

+  * The constructor of `SubString` now checks if the requsted view range


Shouldn't this be listed under "breaking changes", since it can raise an error for previously working cases?

moved, although if someone used an index outside a valid range it was probably a bug

Sure, but that can still break code since no error was thrown before. Anyway, looks good to me now.

stevengj · 2017-10-03T01:53:02Z

base/shell.jl

@@ -65,7 +65,7 @@ function shell_parse(str::AbstractString, interpolate::Bool=true;
                j = k
            end
        elseif interpolate && !in_single_quotes && c == '$'
-            update_arg(s[i:j-1]); i = k; j = k
+            update_arg(s[i:prevind(s, j)]); i = k; j = k


I don't understand why these changes are being made as a part of this PR. What does this have to do with SubString?

If j is the index of c, then j-1 is actually correct for s::String because c=='$' is ASCII, by the way.

There are two reasons:

if j is the index of c if c=='$' then j-1 does not have to be correct. Consider s="∀\$", then j=4 and j-1 is an incorrect index (s[j-1] throws UnicodeError even under stable 0.6 before the changes; the changes only make it also throw an error when range indexing is used e.g. s[i:j-1]).

It is implemented in SubString PR as s is SubString because it is defined as s = lstrip(str) in line 13 and lstrip returns SubString.

@stevengj Is this justification OK?

Right, I was thinking of j+1, not j-1.

nalimilan · 2017-10-12T09:34:26Z

@stevengj Merge now?

nalimilan · 2017-10-13T07:50:35Z

Thanks @bkamins!

kshyatt added the strings "Strings!" label Jun 24, 2017

nalimilan reviewed Jun 25, 2017

View reviewed changes

tkelman reviewed Jun 25, 2017

View reviewed changes

nalimilan reviewed Jun 26, 2017

View reviewed changes

bkamins mentioned this pull request Jun 26, 2017

checkbounds for strings #22548

Closed

nalimilan reviewed Jun 27, 2017

View reviewed changes

tkelman reviewed Jul 2, 2017

View reviewed changes

bkamins mentioned this pull request Jul 2, 2017

Correct length to endof in SubString call JuliaDocs/Documenter.jl#530

Merged

nalimilan reviewed Jul 2, 2017

View reviewed changes

nalimilan requested a review from stevengj September 9, 2017 21:35

bkamins mentioned this pull request Sep 19, 2017

Improvement of the functions for handling string indexing #23765

Closed

bkamins force-pushed the patch-9 branch from 1e7efea to c01dfae Compare September 20, 2017 18:37

nalimilan reviewed Sep 22, 2017

View reviewed changes

nalimilan mentioned this pull request Sep 23, 2017

Improved nextind and prevind #23805

Merged

nalimilan force-pushed the patch-9 branch 2 times, most recently from 76f3966 to 98a1b14 Compare September 23, 2017 10:01

bkamins force-pushed the patch-9 branch from 98a1b14 to 4dc4d5b Compare September 29, 2017 10:38

strict SubString constructor

73de7c2

bkamins force-pushed the patch-9 branch from bf2864e to 73de7c2 Compare September 29, 2017 18:52

bkamins force-pushed the patch-9 branch from d451f7f to 73de7c2 Compare October 1, 2017 12:20

add NEWS.md entry

217d293

nalimilan reviewed Oct 1, 2017

View reviewed changes

NEWS in breaking changes

d79a916

bkamins mentioned this pull request Oct 2, 2017

Add documentation of SubString #23957

Merged

stevengj reviewed Oct 3, 2017

View reviewed changes

stevengj approved these changes Oct 12, 2017

View reviewed changes

nalimilan merged commit 39f668c into JuliaLang:master Oct 13, 2017

bkamins deleted the patch-9 branch October 13, 2017 07:50

nalimilan mentioned this pull request Oct 15, 2017

New failure with regex match including non-ASCII characters #24157

Closed


		@test SubString("∀∀", 4, 4) == "∀∀"[4:4]

		for idx in 5:8

		@@ -238,6 +238,9 @@ Library improvements

		* The functions `strip`, `lstrip` and `rstrip` now return `SubString` ([#22496]).

		* The constructor of `SubString` now checks if the requsted view range

Fixes constructor of SubString from SubString #22511

Fixes constructor of SubString from SubString #22511

Conversation

bkamins commented Jun 24, 2017

nalimilan commented Jun 24, 2017

davidanthoff commented Jun 24, 2017

bkamins commented Jun 25, 2017

nalimilan commented Jun 25, 2017

bkamins commented Jun 25, 2017

davidanthoff commented Jun 25, 2017

bkamins commented Jun 25, 2017

nalimilan commented Jun 25, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Jun 26, 2017

bkamins commented Jun 26, 2017

nalimilan left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Jul 2, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Jul 2, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Sep 20, 2017

bkamins commented Sep 21, 2017

nalimilan left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Sep 22, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins commented Sep 23, 2017

bkamins commented Sep 29, 2017

KristofferC commented Oct 1, 2017

bkamins commented Oct 1, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bkamins Oct 3, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nalimilan commented Oct 12, 2017

nalimilan commented Oct 13, 2017

bkamins Oct 3, 2017 •

edited

Loading