Index conversions are too darn complicated

[mbauman]

I'm entirely at fault for this one, but as a public and documented interface we're fairly constrained in the non-breaking changes we can make. There are two functions and four (!!) levels of indirection here, making things particularly hard to reason about.

• to_indices(A, I::Tuple) — the main entry point. Note that I is a tuple — not a vararg. This is different from nearly all of our other indexing functions.
  • At this point, simple indices that only contain Integers get converted straight away (since calling indices(A) is expensive in some cases)
• to_indices(A, indices(A), I::Tuple) — this is the general form, it recurses through the two types of indices in sync.
  • At this point, multidimensional indices are expanded since they need to walk through multiple dimensions of the parent
  • Also indices like : that need access to the parent's indices in order to expand
• Base.to_index(A::Specialized, I[1]) — for each element of the tuple of passed indices that makes it this far, we allow arrays to specialize their behaviors.
• Base.to_index(I[1]) — and, finally, we allow the index itself to implement a conversion.

Note that Base.to_index is not exported but it's documented as a function you can specialize.

I think we should simplify this for 1.0. The reasons for this design are largely historical, but some of these are still true:

• We used to need to support partial linear indexing, which made the indices(A) computation hard for final :s.
• Ambiguities used to be a PITA. Now I think you'd want to know when there's a conflict and your specialization may not take effect.
• Walking through indices(A) and I together isn't trivial — you need to use something like Base._maybe_tail and such. Unlike the other two, I don't have a good solution for this one, and it makes documenting how to do this very complicated.

Not sure about the best way to resolve this (or if it's even worth futzing about), but I figured I'd open an issue to see what others think.

[timholy]

I think some of the complexity comes from us trying to be reasonably nice to the compiler: march through the indices once, making all the relevant substitutions. What that means is that we have to dispatch on many different possibilities. An alternative (one that may not work) would be to conceive of it as a series of passes: flatten (to expand CartesianIndex), uncolon, etc. I think the main snafu with this plan is Array{CartesianIndex}, which really can't be flattened.

Another potential approach that might help a bit would be to develop a bit more formal structure for tuple operations. In https://github.com/JuliaLang/julia/pull/23867#issuecomment-331834296 it was suggested to expand the tuple interface along such directions. So _maybetail would become drop(t, 1). #23730, #23676, #23659, and #23658 are also aimed at developing more "standard" interfaces for tuples. We've historically "buried" these lispy-tuple methods for fear of extending things inappropriately (perhaps originally inspired by the fact that Base.tail is not exported), but perhaps it's time to change that?

[JeffBezanson]

This can maybe be included in 1.0, but I'd be really careful with priorities here, as time is starting to run a bit short.

[timholy]

If we want to try to solve this by developing a more standard tuple interface, I put up #23875 as a potential prerequisite.

[StefanKarpinski]

Triage essentially reiterates what @JeffBezanson said a week ago: if this gets done, excellent, if not, then we're already in better shape in terms of extensibility compared to every other language. I should also mention that since the top priority for 1.0 is user-level stability, there is some room for evolution of things like extensible indexing as long as it doesn't break too much and we're careful about making sure packages keep working.

[mbauman]

We've been living with this for quite some time now, and I think the API is just fine, especially since maybetail(t) is now just spelled t[2:end].