Nim: [TODO] `BackwardsIndex` should be replaced by something better: `opLen`

[timotheecour]

I don't like BackwardsIndex because:

• it's not transparent: library code must support it as a special overloads for every proc that defines a [] indexing, eg:

proc `[]`*[T](s: openArray[T]; i: BackwardsIndex): T {.inline.} =
  system.`[]`(s, s.len - int(i))
proc `[]=`*[T](s: var openArray[T]; i: BackwardsIndex; x: T) {.inline.} =
  system.`[]=`(s, s.len - int(i), x)

• it's overly restrictive, eg, we can't use arbitrary expressions involving length of underlying container (only things like length - index, not other stuff like length / 2 for example).

Instead some other languages define a special syntax to mean "length" of underlying container dimension, eg:

• in matlab:
  a(1 : end, 1 : end / 2)
• in D:
  a[0..$-1, 0 .. $/2]
  this uses opDollar, for a full documentation see https://dlang.org/spec/operatoroverloading.html#array-ops ; here's a snippet

struct Array2D(E) {
    // Support `$` in slicing notation, e.g., arr[1..$, 0..$-1].
    @property int opDollar(size_t dim : 0)() { return width; }
    @property int opDollar(size_t dim : 1)() { return height; }
}

proposal

Similarly, in Nim, we could allow a user defined opLen (or another name) routine that would be called whenever an expression involves a special symbol, which would allow returning the length of the underlying container or container dimension depending on how it's called, eg:

type Matrix=object
  width:int
  height:int

proc `[]`(m:Matrix, i: int, j: int) = ...

template opLen(m:Matrix, dim: static int): int =
  when dim == 0: m.width
  elif dim == 1: m.height
  else: static: assert false

let m = Matrix(width: 10, height: 20)
discard m[len / 2, len-1]

workaround

I've actually implemented exactly that for a tensor library I'm working on, but it requires using varargs[untyped] parameters, which are then post-processed using some macros that rewrite len using provided opLen. It seems to work quite well, but has the drawback of requiring varargs[untyped] instead of just regular typed parameters.

With compiler support, this wouldn't be needed, and all that would be needed for library code would be to define opLen proc/template for a given type. As in D, it would take 0 or 1 parameter. Happy to explain more if needed, but https://dlang.org/spec/operatoroverloading.html#array-ops should be self explanatory.

[EDIT] other examples

with my proposal, in macros.nim all that's needed is:

proc len*(n: NimNode): int {.magic: "NLen", noSideEffect.}
  ## returns the number of children of `n`.

proc `[]`*(n: NimNode, i: int): NimNode {.magic: "NChild", noSideEffect.}
  ## get `n`'s `i`'th child.

which would allow, under this proposal, arbitrary operations, eg: n[len-1]

but with existing solution, we need, on top of these, the following:

proc `[]`*(n: NimNode, i: BackwardsIndex): NimNode = n[n.len - i.int]
  ## get `n`'s `i`'th child.

template `^^`(n: NimNode, i: untyped): untyped =
  (when i is BackwardsIndex: n.len - int(i) else: int(i))
proc `[]=`*(n: NimNode, i: BackwardsIndex, child: NimNode) =
  ## set `n`'s `i`'th child to `child`.
  n[n.len - i.int] = child

[mratsim]

^1 was such a compiler magic before and I had issue in Arraymancer due to it because it didn't work for multidimensional indexing.

Obviously if it's user-defined it would be much better but I'm wary of introducing len as a keyword and an opLen magic. First it would break all libraries using len already, second opLen is magic.

[hlaaftana]

There was a proposal for a ^^ overload that solves both your issues, but I don't remember where it came from or what it looked like originally, so this is a mockup of what I think it looked like.

template `^`*(i: int): BackwardsIndex =
  BackwardsIndex(i)

template `[]`*[T](s: T, i: BackwardsIndex): untyped =
  s[s ^^ i]

template `^^`*[I, T](s: array[I, T], i: BackwardsIndex): int =
  low(s) + len(s) - int(i)

template `^^`*[T](s: openarray[T], i: BackwardsIndex): T =
  len(s) - int(i)

I actually really like BackwardsIndex, and going back to compiler magic would just make things harder for me.

[Araq]

No magic, been there, done that, was worse than the solution we have today.

[zah]

Here is example of the ^^ solution mentioned above:

https://github.com/status-im/nim-ranges/blob/master/ranges/typedranges.nim#L144

The idea is that you can handle all kinds of combinations of forwards and backwards indices with the same template.

[timotheecour]

There was a proposal for a ^^ overload that solves both your issues

doesn't look like it's solving the 2nd issue I mentioned: BackwardsIndex is still overly restrictive, and you can't write a(1 : end, 1 : end / 2) with it (only expressions of the form index or length - index, not any other expression such as length / 2). As for the 1st issue, the approach using ^^is more complex than the way I proposed in Nim via opLen (or end in matlab, or $ in D).
Note, again, that it already works today in Nim (which is what I did), but requires using untyped; compiler support would alleviate that, and all a library would have to define is a single opLen(CustomType) or opLen(CustomType, dim: int); everything else would just deal with regular int indexes; much simpler than the workarounds mentioned in this thread in which every BackwardsIndex, ^^ etc appear in many places.

eg: here's how https://github.com/status-im/nim-ranges/blob/master/ranges/typedranges.nim#L144 would simplify:

template `^^`(s, i: untyped): untyped =
  (when i is BackwardsIndex: s.len - int(i) else: int(i))

proc `[]`*[T, U, V](r: Range[T], s: HSlice[U, V]): Range[T] {.inline.} =
  sliceNormalized(r, r ^^ s.a, r ^^ s.b)

proc `[]`*[T, U, V](r: MutRange[T], s: HSlice[U, V]): MutRange[T] {.inline.} =
  MutRange[T](sliceNormalized(r, r ^^ s.a, r ^^ s.b))

proc `[]=`*[T, U, V](r: MutRange[T], s: HSlice[U, V], v: openarray[T]) =
  let a = r ^^ s.a
  let b = r ^^ s.b
  let L = b - a + 1

would simplify to:

template opLen[T](r: Range[T]): int = r.len # that's the only definition needed to support arbitrary expressions eg `foo[len/2]`

proc `[]`*[T, U, V](r: Range[T], s: HSlice[U, V]): Range[T] {.inline.} =
  sliceNormalized(r, s.a, s.b)

proc `[]`*[T, U, V](r: MutRange[T], s: HSlice[U, V]): MutRange[T] {.inline.} =
  MutRange[T](sliceNormalized(r, s.a, s.b))

proc `[]=`*[T, U, V](r: MutRange[T], s: HSlice[U, V], v: openarray[T]) =
  let L = s.b - s.a + 1

[krux02]

I have already a PR that solves the issue with the BackwardsIndex here: https://github.com/nim-lang/Nim/pull/7265

Please write in that PR if such a solution is suitable for you.

[timotheecour]

The points I raised in https://github.com/nim-lang/Nim/issues/9025#issuecomment-424297266 still apply with your PR:
your PR fixes a bug in BackwardsIndex but the issue I present here still remains; BackwardsIndex and ^^ is both more restrictive and more complicated than what I suggest here (and that already exists in D based on opDollar)

[Araq]

What you suggested here is what we tried first. And it worked worse, compiler complexity vs stdlib complexity.

[krux02]

@Araq can I close this as rejected then?

[Araq]

Hmm yeah.