Make view of range with range be a range

[andyferris]

I had brought this one up on Slack a few months ago.

Typical AbstractRange types are compact and immutable, and we can remove the overhead of SubArray in this case while the cost of view remains O(1).

New behavior:

julia> view(1:10, 1:10)
1:10

[andyferris]

Bump

[mbauman]

Yeah, I think I'm in favor here. We should probably also document this constraint for AbstractRange — that indexing a range by a range must return a range — but unfortunately we don't have any existing documentation there, so that's a bigger ask.

[andyferris]

Before merging - I'm wondering now about some of the floating-point unit ranges. Is it really even possible for all of these getindex operations to return an AbstractRange? Some algorithms go through hoops to hit their end points but I wonder if a subset of a LinSpace is necessarily a LinSpace (to full floating point precision), for example.

One option is to limit this signature to integer ranges... thoughts?

[mbauman]

Yes, that's a good consideration. I'm not sure, either. We could simply duplicate the getindex signatures we have. That's probably the best option.

julia> methods(getindex, Tuple{AbstractRange, AbstractRange})
# 8 methods for generic function "getindex":
[1] getindex(r::Base.OneTo{T}, s::Base.OneTo) where T in Base at range.jl:537
[2] getindex(r::AbstractUnitRange, s::AbstractUnitRange{#s57} where #s57<:Integer) in Base at range.jl:529
[3] getindex(r::AbstractUnitRange, s::StepRange{#s57,S} where S where #s57<:Integer) in Base at range.jl:543
[4] getindex(r::StepRange, s::AbstractRange{#s57} where #s57<:Integer) in Base at range.jl:550
[5] getindex(r::StepRangeLen{T,#s57,#s56} where #s56<:Base.TwicePrecision where #s57<:Base.TwicePrecision, s::OrdinalRange{#s55,S} where S where #s55<:Integer) where T in Base at twiceprecision.jl:460
[6] getindex(r::StepRangeLen{T,R,S} where S where R, s::OrdinalRange{#s57,S} where S where #s57<:Integer) where T in Base at range.jl:557
[7] getindex(r::LinRange, s::OrdinalRange{#s57,S} where S where #s57<:Integer) in Base at range.jl:567

[andyferris]

I've now specialized on the first three four - the typical integer cases. Unlike my earlier approach, this should at least be perfectly safe.

[JeffBezanson]

Bump. Seems useful.

[mbauman]

Agreed! Let's do this. Needs a rebase. Also, do we now need NEWS? How conservatively are we going to be with regards to annotating changes like this that change types but not behavior in 1.x?

[timholy]

I like it now that it's safe. Like @mbauman, my head spins with questions about whether changing return type is a breaking change.

[JeffBezanson]

I think it's too breaking for a 1.0.x release, but might be ok for 1.1. In particular it's ok if the new type supports the same interface as the old one.

[andyferris]

Cool.

Do we have a branch for 1.1 for this to target?

[andyferris]

I think the problem of answering the question “how breaking it is this?” is that we don’t have a rigorous software engineering answer to “what is an interface?”

Ideally the type system or something would check that you haven’t changed the interface of the return type that you have documented as that which should be assumed by the user of your function. Or something - it’s a tricky thing, it seems.

In this case what is the interface assumed by a view? That it is cheap (O(1) and no large memory allocations)? That it tracks mutations to the parent? Both? Something else? How is this documented and how could this possibly be verified by tests or the type system or the compiler?

Tricky, tricky.

[StefanKarpinski]

Since this is technically breaking I think it should definitely not be done in a point release—so not in a 1.0.x release. However, if we run PkgEval on the entire registered ecosystem and nothing breaks, I think we should go ahead with it in a 1.x release. I feel that we should take this approach in general: anything that is mildly technically breaking but doesn't actually break any packages can be changed in a minor release.

[fredrikekre]

It could still break things in the future.

[StefanKarpinski]

Yes, of course, that's what "technically breaking" means—that something could potentially break. The point of running PkgEval on all registered packages is to see if people seem to actually be relying on the behavior that is changing. If not a single registered package is, that's strong evidence that in practice no one cares about the behavioral change and therefore it's ok to make it.

Keep in mind that all changes are potentially breaking, including so-called "bug fixes", which are just breaking changes where we have made a judgement call that no one is likely to have been relying on the old behavior. Making no changes to the language that could potentially break anyone's code would mean not changing anything at all, which is clearly not desirable or practical.

[mbauman]

Triage generally liked this — it just needs a rebase and NEWS.

While technically breaking, this is going from a more complicated (immutable) AbstractArray to a much simpler (immutable) one. If folks are dispatching on a particular AbstractArray type in the first place, they'll probably like this even better.

[JeffBezanson]

Bump

[mbauman]

Looks like we're missing a few methods here:

julia> for m in methods(getindex, Tuple{AbstractRange, AbstractRange})
           tt = Base.tuple_type_tail(m.sig)
           tt == Tuple{AbstractArray,Vararg{Any,N}} where N && continue
           vmt = collect(methods(view, Tuple{AbstractRange, AbstractRange}))
           vm = findfirst(sig->tt <: Base.tuple_type_tail(sig.sig), vmt)
           if vmt[vm].sig == Tuple{typeof(view),AbstractArray,Vararg{Any,N}} where N
               println(tt)
           end
       end
Tuple{StepRangeLen{T,#s75,#s74} where #s74<:Base.TwicePrecision where #s75<:Base.TwicePrecision,OrdinalRange{#s73,S} where S where #s73<:Integer} where T
Tuple{StepRangeLen{T,R,S} where S where R,OrdinalRange{#s75,S} where S where #s75<:Integer} where T
Tuple{LinRange,OrdinalRange{#s75,S} where S where #s75<:Integer}

The above should probably be converted into a unit test.

[StefanKarpinski]

Bump. This seems like it would be good to go with Matt's comment addressed.

[mbauman]

I added the missing methods, a test, and NEWS. The win32 failure looks unrelated — this is now good to go!

[andyferris]

Awesome - thanks Matt!