On the release notes for version 0.18 there is this backwards incompatible change:
We changed how array accesses “from backwards” like a[^1] or a[0..^1] are implemented. These are now implemented purely in system.nim without compiler support. There is a new “heterogenous” slice type system.HSlice that takes 2 generic parameters which can be BackwardsIndex indices. BackwardsIndex is produced by system.^. This means if you overload [] or []= you need to ensure they also work with system.BackwardsIndex (if applicable for the accessors).
It says we need to ensure that, but there is no documentation on how to "ensure" our [] overloads that worked before with ^ continue working now. It seems we need to type more boilerplate now when doing that type of overload, but what? Extra overloads? Code inside the existing overloads to handle BackwardsIndex? I don't know. I'm supposed to always call mymodulename.`[]` when inside my module to ensure the correct handling of BackwardsIndex (issue: https://github.com/nim-lang/Nim/issues/6692 )? I don't know.
Also, the the Slice and HSlice documentation on system.nim is lacking. It's basically tautology. There is no indication on why one should use one over the other. In what situations one is more adequate than other. Or what exactly they are. Can T and U be floats or pointers, for example? I guess they could, based on the type implementation. Other languages use the word slice to mean exclusively a pointer + lenght pair, or pointer + pointer pair.
Also, is there any example of data structure where normal indexing and slicing is fine but backwards index isn't also trivially fine? I never had problems with the way backwards indexing worked before, but I wanted to know what triggered that change. It would be nice if there were links in the release notes to the github bug/commit/pull request that introduced the changes.
I am not an experienced Nim user, but I can answer few of your questions.
Also, the the Slice and HSlice documentation on system.nim is lacking. It's basically tautology. There is no indication on why one should use one over the other.
From the documentation, Slice[T] is an alias for HSlice[T, T]. By definition, HSlice allows its two elements to be of different types (HSlice[T; U]) - heterogeneous. But Slice is a special type of HSlice where both the types are same.
In what situations one is more adequate than other.
I think that the decision to use Slice over HSlice would be code clarity. When one sees that the type is Slice, they would know immediately that both elements of that object need to be of the same type. If you don't set them to be of the same type, you will get a compilation error.
Here are my notes on those two:
Are they supposed to be produced only by the .. and related operators from system?
No. You can create hslices in a more verbose manner too (see below). The .. just makes it very convenient.
var s1: HSlice[int, char]
s1.a = 4
s1.b = 'f'
echo s1
let s2 = 4 .. 'f'
echo s2
echo s1 == s2
Above outputs:
(a: 4, b: 'f')
(a: 4, b: 'f')
true
Can T and U be floats or pointers, for example? I guess they could, based on the type implementation.
Yes. See my HSlice notes linked above. They don't have T and U of those exact types. But I do have examples with those of different types.
For BackwardsIndex, looking at this section, we can see how to use backwards int. It's also worth mentioning that BackwardsIndex is simply a distinct int, which exists solely for the purpose of knowing what the meaning of that int is, so you can do something useful with it.
Here is some sample code using a simple linked list.
type
Node = ref object
data: string
next: Node
proc hasNext(node: Node): bool =
## Helper proc for seeing if the list has a next item
not node.next.isNil
proc len(node: Node): int =
## Get the length of the linked list
result = 1
var tmp = node
while tmp.hasNext:
result += 1
tmp = tmp.next
# In Nim < 0.18.0, this is all you would need to define because the compiler would
# translate ^2 to len(list) - 2. Now you must implement your own. See below
proc `[]`(node: Node, i: int): Node =
result = node
for _ in 0 ..< i:
if result.hasNext:
result = result.next
else:
raise newException(IndexError, "Index out of range!")
# This new proc must be used if you want to support Backwards indexing
proc `[]`(node: Node, i: BackwardsIndex): Node =
# BackwardsIndex is really just a distinct int type,
# so we can convert it here with no issues
let realIndex = node.len() - i.int
result = node[realIndex]
var node = Node(
data: "mydata",
next: Node(
data: "mydata2",
next: Node(
data: "mydata3",
next: nil
)
)
)
echo node.len()
echo node[0].data
echo node[1].data
echo node[^1].data
echo node[^2].data
# Prints:
# 3
# mydata
# mydata2
# mydata3
# mydata2
You can see in the example linked list above that it might not be okay for the compiler to assume that len is defined. It could also be less efficient to do it automatically. So the way it is implemented now gives freedom to the programmer to make backwards indexing more efficient or whatever additions they want. Using a different algorithm in the backwards indexing above, I could make it more efficient without using len(), since it's an O(n) operation.
You'll notice that I'm reusing the non backwards index [] proc in the backwards index [] proc. But I don't have to now. With the previous implementation, you were kind of locked into using what the compiler did.
So now I can do something like this:
proc `[]`(node: Node, i: BackwardsIndex): Node =
var
index = i.int
# Keep track of left and right indices
nodeLeft = node
nodeRight = node
while nodeRight.hasNext:
nodeRight = nodeRight.next
if index > 1:
index -= 1
else:
nodeLeft = nodeLeft.next
if index > 1 and not nodeRight.hasNext:
raise newException(IndexError, "Index out of range: ^" & $i.int)
result = nodeLeft
For reference, here's one of the commits that introduced BackwardsIndex. Maybe it will help?
Unfortunately, I'm not sure about your other question. Looking at the source doesn't help too much either, because to me it is unclear when HSlice is needed vs Slice.
I guess HSlice may be needed to handle indexing where one of the extremes is a normal index, while the other one is a backwards index, such as x[1 .. ^1].
To handle this, one would have to implement proc `[]`(x: MyDataStructure, s: HSlice[int, BackwardsIndex]
@kaushalmodi those are some really useful notes. Because of them I think I understand HSlice and Slice now!
@andrea, cool. That makes a lot of sense. Add that to my list of cool stuff Nim can do.
@Araq, thanks for the kind words! Unfortunately, I'm swamped with trying to get my nim-libnx library to work and writing tests for the forum :)
Thanks for all answers and sorry for the late reply.
At first I tried creating new overloads semi-ignored the HSlice problem. Semi-ignored because now the '..' and related operators from system always return a HSlice instead of a slice, even if both sides are regular indexes. So I changed the type to accept HSlice[SomeInteger, SomeInteger], but not the implementation. This satisfied me for a while, but now I came back to implement the BackwardsIndex for slices and the previous overload solution simply doesn`t scale well.
I then used jypayne link to see how that change was made in the standard library, and found the ^^ helper template, that is indeed very useful, especially with the following concept:
type SomeIndex = SomeInteger | BackwardsIndex
template `^^`(s, i: untyped): untyped =
(when i is BackwardsIndex: s.len - int(i) else: int(i))Using them updating the functions is just a matter of updating the index/bounds type and prepending s^^ (or whatever the name of your first argument) to every use of the index/bounds type. No overloading needed, just two functions for indexing (and one for slicing):
proc `[]`*[T](s: MemView[T], i: SomeIndex): var T {.inline.} =
## Mutable array like access of element ``i``.
xBoundsCheck(s, s^^i)
result = s.data[s^^i]
proc `[]=`* [T] (s: MemView[T], i: SomeIndex, val : T) {.inline.} =
## Change element ``i`` of the view.
xBoundsCheck(s, s^^i)
s.data[s^^i] = valI think there is no need for defining a indexing one with non var T result, right?
And the example usages were also interesting. I always thought about hash table indexes as a "key", so it did not come to my mind this problem. Those infinite/sparse structures can indeed have problems with backwards indexing. And on the other hand, the linked list that has slow general indexing, but fast last and first element indexing, can also benefit from this change, as jyapayne showed.