Add inbounds annotation to safe iteration

[timholy]

#40397 was a recent discussion of the issue of adding @inbounds to the generic fallback for iterate on AbstractArray. As pointed out there, since iterate is a public function, there's no reason to believe that users won't call it with broken arguments, and hence trusting that it's inbounds is very problematic.

However, that doesn't prevent us from adding annotations via known-safe callers. Here are some cases (feel free to add more):

• T[v[i] for i in idx]: this can be solved by changes mostly to lowering (see below for details)
• [v[i] for i in idx]: also fixable by lowering, but it's a very different solution despite superficial similarity to the above (see below)

Lowering of T[v[i] for i in idx]

julia> Meta.lower(Main, :(T[v[i] for i in idx]))
:($(Expr(:thunk, CodeInfo(
     @ none within `top-level scope`
1 ──       Core.NewvarNode(:(#s1))
│          Core.NewvarNode(:(@_2))
│          Core.NewvarNode(:(@_3))
│    %4  = idx
│    %5  = Base.IteratorSize(%4)
│    %6  = %5 isa Base.SizeUnknown
└───       goto #3 if not %6
2 ── %8  = Core.apply_type(Core.Array, T, 1)
│          @_3 = (%8)(Core.undef, 0)
└───       goto #4
3 ──       @_3 = Base._array_for(T, %4, %5)
4 ┄─ %12 = Base.LinearIndices(@_3)
│          @_2 = Base.first(%12)
│          #s1 = Base.iterate(%4)
│    %15 = #s1 === nothing
│    %16 = Base.not_int(%15)
└───       goto #10 if not %16
5 ┄─ %18 = #s1
│          i = Core.getfield(%18, 1)
│    %20 = Core.getfield(%18, 2)
│    %21 = Base.getindex(v, i)
│          $(Expr(:inbounds, true))
└───       goto #7 if not %6
6 ──       Base.push!(@_3, %21)
└───       goto #8
7 ──       Base.setindex!(@_3, %21, @_2)
8 ┄─       $(Expr(:inbounds, :pop))
│          @_2 = Base.add_int(@_2, 1)
│          #s1 = Base.iterate(%4, %20)
│    %30 = #s1 === nothing
│    %31 = Base.not_int(%30)
└───       goto #10 if not %31
9 ──       goto #5
10 ┄       return @_3
))))

We could check bounds and then branch to an implementation that also inbounds the Base.getindex(v, i) call. If folks are worried that this might essentially be two loops and hence slower (though that's not obvious), with #42029 there will be many cases where bounds-checking on idx will be much faster than iterating over the whole thing. We could introduce a call to CheckIndexStyle(idx) and, if something promising comes back, use the @inbounds branch.

Lowering of [v[i] for i in idx]

While the lowering looks simpler, this is actually going to be the harder case to handle:

julia> Meta.lower(Main, :([v[i] for i in idx]))
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope`
1 ─      $(Expr(:thunk, CodeInfo(
    @ none within `top-level scope`
1 ─      global var"#5#6"
│        const var"#5#6"
│   %3 = Core._structtype(Main, Symbol("#5#6"), Core.svec(), Core.svec(), Core.svec(), false, 0)
│        var"#5#6" = %3
│        Core._setsuper!(var"#5#6", Core.Function)
│        Core._typebody!(var"#5#6", Core.svec())
└──      return nothing
)))
│   %2 = Core.svec(var"#5#6", Core.Any)
│   %3 = Core.svec()
│   %4 = Core.svec(%2, %3, $(QuoteNode(:(#= none:0 =#))))
│        $(Expr(:method, false, :(%4), CodeInfo(
    @ none within `none`
1 ─ %1 = Base.getindex(v, i)
└──      return %1
)))
│        #5 = %new(var"#5#6")
│   %7 = #5
│   %8 = Base.Generator(%7, idx)
│   %9 = Base.collect(%8)
└──      return %9
))))

This defines an inner function to perform the v[i] and then dispatches to the generator framework. We could instead create a vindxer = GetIndex(v) so that vindexer(i) returns v[i]. (Do we already have that somewhere? It's not coming to mind.) Then collect could dispatch specially on Generator{I,<:GetIndex} objects. So much of the work here is on the Julia side (hence, I could handle that), but it will require changes to lowering which I refuse 😈 to figure out how to make as long as that code is in lisp.

[tkf]

Let me mention that I didn't object to #40397 being closed since I had a solution in mind and wanted to re-open it with a concrete implementation.

since iterate is a public function, there's no reason to believe that users won't call it with broken arguments

I don't think this is an ideal direction for formalizing fundamentally performance-sensitive protocol like iterate. We need to accurately specify what is considered a public interface and what is not. Touching internals of object is considered unsafe:

julia> a = view(ones(3), [1])
       a.indices[1][1] = 2^30
       a
1-element view(::Vector{Float64}, [1073741824]) with eltype Float64:

signal (11): Segmentation fault

Similarly, I think it makes sense to treat the state object of iterate as internal and opaque. It would be nice to clearly state this in the documentation. I hope we can develop more formal aspects in our protocol design so that we can deal with narrow contract APIs.

tl;dr: Not all operations on the returned value of a public interface are public.

Having said that, I agree that it is desirable to have optional safeguards for making it hard to misuse the protocol and gracefully fail whenever possible.