ReversedCollection.subscript inconvenience

(Anthony Latsis) #1

I was struggling to subscript a reversed array with ReversedIndex today, and then discovered this. That can't possibly be correct, can it?

The main reason I created this topic though is that I think the following is unacceptable effort just to subscript a reversed collection with a trivial base index, like an Array.

let reversedArray = [1, 2, 3, 4, 5].reversed()
let last = reversedArray[ReversedCollection.Index(0)]

This might as well apply to other APIs that use ReverseCollection.Index. I suspect source compatibility does not allow us to redesign ReversedCollection to use the base index type, but does adding subscript(Base.Index) sound like a reasonable suggestion?

(Nate Cook) #2

What’s your expected result for reversedArray[0]? Would you expect that to be the first element in the reversed array (5), or the element at that index in the base collection (1)?

There are definitely weird ergonomics around ReversedCollection indices that I wish we had fixed (your example should trap, since that’s effectively the same as writing array[-1]). The biggest problem with sharing indices with the base collection is that there isn’t a clear answer for how to provide an endIndex for the reversed collection. That’s the source of the off-by-one strangeness of ReversedCollection.Index in the first place, and removing that index type’s opaqueness would make things more confusing, not less.

2 Likes
(Nate Cook) #3

Also yes, that should alias ReversedCollection<T>.Index! I don’t think that’s fixable at this point, but since that type alias is unusable in Swift 5+, the impact is probably low.

(Ben Cohen) #4

I think there's a bigger problem – how would < work?

1 Like
(Ben Cohen) #5

The thing that's not right being:

public typealias ReversedIndex<T: BidirectionalCollection> = ReversedCollection<T>

Oh wow, no, that is definitely a bug. That said, it does no real harm except confusing the heck out of anyone who might try to use that type alias (which is itself pretty unlikely – those aliases are mostly going-through-the-motions additions for source compatibility).

1 Like
(Ben Cohen) #6

It's fixable. Type aliases aren't in the ABI.

7 Likes
(Anthony Latsis) #7

I would expect it to return the first element in the reversed collection, which is 5.

I see, thanks for clarifying. It seems the only real pain is creating indices, which is mostly subscripting, especially considering the special rules on ReversedCollection.Index.

Good to hear. I'll go ahead and open a PR, then.

1 Like
(Xiaodi Wu) #8

I disagree. The overall design of Swift collections is such that indices are shared with the base collection. If this expression compiled, I would expect it to return the first element in the base collection.

Where there is ambiguity (such as in the case of subscripting ranges), Swift disables this subscripting syntax, which I think is appropriate here.

1 Like
(Anthony Latsis) #9

But you would be subscripting the reversed collection, the existence of _base is an internal implementation detail the user is not required to know about. The fact that we can't use the same index type is just a shortcoming of the model – it would only be natural to be able to use them.

(Xiaodi Wu) #10

Whether the base is accessible publicly or not is beside the point. The existence of a base collection isn’t an implementation detail: it’s essential to the semantics of the type. Otherwise, there would be no sense in which the collection could be said to be reversed.

There isn’t any technical reason why we couldn’t (before ABI stability) have used the same index type; however, if we did, I would expect the sharing of indices and not merely of the type.

#11

I see your point from a library author's perspective, but from a regular developer's perspective, I'd expect the following two variables to behave identically:

let x = [1, 2, 3, 4, 5].reversed()
let y = Array([1, 2, 3, 4, 5].reversed())

That is, they should both be simple bidirectional collections with an integer Index type. Collection slicing is explicitly called out in the documentation to be a view on top of the original collection. Is there similar documentation for reversed()?

(Ben Cohen) #12

There is. Their index Comparable semantics would be busted.

4 Likes
#13

Is the semantic requirement “startIndex <= endIndex” documented anywhere?

Edit: or more generally, “i <= index(after: i)

(Ben Cohen) #14

I think we have to draw a line somewhere regarding obviousness of certain requirements. Overly verbose and pedantic documentation isn't useful.

#15

Perhaps, but I don’t think this is such a case, especially given the existence of ReversedCollection.

If the protocol requires that index values increase as they advance, that should be documented.

(Nate Cook) #16

That seems like a reasonable thing that should be documented. I could see that going into the index(after:) docs and the “Conforming to the Collection Protocol” section of the Collection overview.

1 Like
(Nate Cook) #17

To the original question, @anthonylatsis, could you say more about your use case for this functionality? What were you trying to do that necessitated looking up elements in the reversed collection by index?

(Ben Cohen) #18

Behave identically in which respect – that indices point to the same location or that indices start at low numbers and increase to higher numbers? You can't have both, despite both being reasonable expectations. The type system helps prevent you from making the mistake of thinking you can rely on the former, whereas the latter is really non-negotiable.

#19

Calling map() on an array gives a new array, with no connection to the old. Same for filter(). Just because reversed() can be optimized by giving a view into the original collection does not mean I expect it to behave differently than the other methods which return fully-functional arrays.

In the example I gave above, I would expect x[0] == 1 and y[0] == 5. I don't really care how that is arranged.

To my mind, the type system is helping to prevent a mistake that is only caused by an implementation detail.

(Ben Cohen) #20

But for other users, the desire to provide a slightly simpler interface for no particularly good reason at considerable and otherwise unnecessary performance cost (i.e. by creating full copy of the collection, a very expensive operation) would be a poor choice.