SE-0265: Offset-Based Access to Indices, Elements, and Slices

The review of SE-0265: Offset-Based Access to Indices, Elements, and Slices begins now and runs through October 21st, 2019.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to the review manager via email or direct message on these forums. If you do send me email, please make sure that "SE-0265" is in the subject.

What goes into a review of a proposal?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift.

When reviewing a proposal, here are some questions to consider:

  • What is your evaluation of the proposal?

  • Is the problem being addressed significant enough to warrant a change to Swift?

  • Does this proposal fit well with the feel and direction of Swift?

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Thanks in advance for your review.

John McCall
Review Manager

18 Likes

I think this is a long overdue proposal that has gone through many, many different iterations over the years. And I'm very happy where this has ended up! Kudos to everyone who has contributed to this design space over the years!

Overall I think this is something that has been missing from Swift since inception, which has led to countless gotchas for beginners used to indexing in just about any other language other than Swift. I think time has shown that while Swift's index design is good, adding this functionality will fill a big hole in usability.

2 Likes

One focused comment: I do think there should be a bit more discussion about ABI here. (Maybe the titles "ABI stability" and "API resilience" are misleading; "backwards-compatibility and library evolution" might have been more interesting.) Here are some notes on that:

  • Because _reverseOffsetIndex(_:by:) is a new requirement, any Collections in existing binary frameworks will be stuck with the minimal default implementation, even if they are bidirectional or random-access collections. Binary frameworks will have to be recompiled to pick up the proper bidirectional implementation. (That is, the runtime will not do overload resolution to pick a default implementation for you.)

  • The new performance characteristics of existing methods are only available on systems with an SE-0265-capable standard library. We should probably document that. (This is also a reason to potentially reconsider "Finally, BidirectionalCollection’s overloads are obsoleted in new versions as they are fully redundant with Collection’s." EDIT: I misread the "in new versions".)

6 Likes

Big +1!

It's long been clear a more user-friendly API for collection indices is needed. This approach keeps the "correctness" of the current version, but also gives an API that is significantly improved. It's also arguably more human readable than a simple integer index while not being verbose. I think I even agree with the naming! :joy:

1 Like

I really think we need more convenient APIs for collections, but I'm not convinced that this proposal is the best solution.
There are alternatives which allow context-sensitive anchors, thus offering much more flexibility. Those alternatives might have serious downsides as well, and if somebody can present me a proper rationale, I'd certainly support SE-0265 as an improvement of the status quo.
However, that didn't happen yet, so currently I'm firmly against this proposal.

What is that alternative?
The current proposal has two possible anchors (.first and .last). For arbitrary collections, there's not much we can do here, but in many cases (String as the most prominent example), there way more than only those two positions:
You might want the index of the first Double that's bigger than a given threshold, or the first character in a string that can be converted to a number...

It would still be possible to use

(line[.first + 5]!, line[.last - 11]!)

but you could also create expressions like

let value = line[.find("=") ..< before(";")]

Here, instead of an enum, .first and .last are static var properties of RelativeIndex, and find would be a static func of that type - and with extensions, you could have as many of those as you like.
There's a prototype of this alternative design, and I think its extended capabilities shouldn't be discarded without even talking about them.
The odd thing for me is that [Prototype] Protocol-powered generic trimming, searching, splitting, basically has all those features which could also be used for basic indexing into collections as well :confused:

4 Likes

All that sounds like it could pitched in a follow-up pitch. The current solution is fairly targeted, and I feel like it'd be harder to sell with more (and harder to define things) added in.

1 Like

I've been following this discussion for a while and I really like where the proposal ended up! I'd be happy to see this make it in as is.

I can't agree: Of course, it's possible to bolt yet another subscript onto Collection, but I don't see how the proposal could be extended.
OffsetBound is neither a protocol nor a class — it's a struct, so afaics our options are very limited without fundamentally changing the proposed design.

2 Likes

Or the API you're talking about, (which arguably shouldn't be a subscript), could be it's own struct/enum and extensions could be added enabling them to co-mingle, and/or a unifying protocol written that they both adhere to.

I'm definitely all for the design being flexible, but there are options and it could take years to decide all the possible capabilities the feature could support. Given it's already gone through multiple rounds of pitch iterations and this is a sorely needed (basic) feature, re-working the design at this stage to possibly better support a uncertain-yet-to-be-accepted feature seems unnecessary :slightly_smiling_face:

1 Like

Isn’t it the purpose of the review to consider alternative approaches, and opportunity costs?

9 Likes

Where is the prototype? And wouldn't this run into exactly the same issues discussed here with generic operator overloading and Comparable conformance? All the nice parts of this OffsetBound proposal seem to stem from the fact that they aren't tied to a collection at all (i.e. don't have generic parameters representing the collection or its element type), so I'm not sure how you can easily fit things like .find("=") in (unless it's .find(Any) with some form of casting).

1 Like

https://github.com/tinoheth/RelativeRanges (prototype means prototype ;-)

Comparable conformance isn't possible, but it's also not required for a working setup. What's the real benefit of pretending to be comparable?

I wouldn't say that all the nice things depend on OffsetBound having no generic parameters. Two unique benefits of the proposed design are serializability and the option to use the same OffsetIndex for completely different collections (like getting the third element of a String and a list of Double).
Are there any other advantages that rely on this freedom?

The purpose of the review is to figure out what to do with the proposal. If you feel that there are reasonable alternatives that should be considered more closely, that's very useful feedback. However, not all alternatives are reasonable; counter-proposals that seem largely speculative or which would depend on major new language/library work that isn't otherwise well-motivated are likely to be ignored. (None of this should be taken as a comment on your counter-proposal, which I haven't looked into; I'm just responding to your question in the abstract and trying to lay down some guidelines about how to make a credible counter-proposal in a review.)

4 Likes

Thinking about it, it also makes it impossible to do something like collection[(.last - 10) ... (.start + 10)], which isn't a very common use-case at all but still...

3 Likes

As I mentioned above, these issues/benefits/advantages are discussed in the proposal, particularly the section I linked. I can see in your prototype that you've already run into the same issues, requiring the creation of a new RelativeRange type and creating a large set of overloads for the range operators (e.g. 5 new overloads for ..., if I counted correctly).

  • What is your evaluation of the proposal?

+1. This is a really nice design that addresses the use cases I'm aware of with clarity and reasonable concision. All of the iterations and hard work have paid off well!

I do have one minor point for discussion. I'm not entirely comfortable with the Comparable semantics of OffsetBound. Quoting from the docs:

/// Offsets relative to `.first` are always less than those relative to
/// `.last`, as there are arbitrarily many offsets between the two
/// extremities. Offsets from the same bound are ordered by their
/// corresponding positions.

This approach makes sense if there are infinitely many offsets between the two extremities. But there aren't. There are an arbitrarily, but finitely many offsets between the extremities. This means that in practice, in the context of specific a collection it is quite possible for an offset anchored by .last to precede an offset anchored by .first. Offsets will generally be manipulated in the context of a specific collection, so this seems somewhat problematic.

Maybe this is acceptable because it allows the design to use RangeExpression, but this is an aspect of the design that should be considered very carefully.

  • Is the problem being addressed significant enough to warrant a change to Swift?

Yes, this proposal addresses the verbosity of index manipulation in usage contexts in an elegant way. In doing so, it also steers people away from the much-discussed foot guns lurking in Int-indexed collections.

  • Does this proposal fit well with the feel and direction of Swift?

Very much so.

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I have used languages with similar collection subscripting features. When you need to do this kind of offset-based subscripting it definitely beats writing boilerplate-y index manipulation code.

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

I have followed the previous discussion threads moderately closely. Well enough to be confident that the design has been through plenty of iterations and reached a pleasing set of tradeoffs.

3 Likes

Part of what solves this for me is that just like an open range expression 3... isn't actually infinite when applied to a specific Collection, .last - 2 isn't necessarily ahead of .first when applied to a specific Collection. If offsets had next and previous properties, no amount of applying next on a first-based offset would ever get you to a last-based offset. In that sense, it's reasonable to say that there are indeed infinitely many OffsetBound values between the two extremities, even though some of them may alias when applied to particular collections.

I don't disagree that it's tricky, and it is still valid to say that because of that it'd be better to not make OffsetBounds Comparable—not because they don't have reasonable semantics, but because it's still a potential pitfall. I think it's net worth-it, though (and presumably so does the proposal author).

What might help is documenting the semantics when an OffsetBound-based RangeExpression accidentally crosses the beginning and end bounds. Since it's tricky and awkward to correctly check for this before using one of the members that takes such a range, I think I suggest treating it like an empty subrange. But whatever the answer is, it should probably be specified explicitly.

4 Likes

I think it's certainly a reasonable tradeoff to make. I don't have a clear position on this (I'm happy I don't have to take one!). I just wanted to call out a particularly tough tradeoff and make sure it gets scrutinized carefully.

If I thought people would often be writing code that actually compared OffsetBound I would be opposed to the Comparable conformance. But its main use is to create ranges rather than to make direct comparisons. I don't think collapsing to an empty range like you suggest has the same potential for surprise that direct use of < does. That being the primary use case makes it more acceptable.

That’s an interesting point. I agree about documenting it somehow. @nnnnnnnn , what do you think the best convention would be? A note at the end of the doc providing a Complexity section for older OSes?

(note that the default implementation of _reverseOffsetIndex is still O(1) for random-access collections, as its implemented in terms of distance and index(_:offsetBy:))

How do you feel about the following phrasing, sticking it under “Effect on ABI stability”?

Collection types defined in previously-compiled binaries would use the default Collection implementation of _reverseOffsetIndex until recompiled, giving O(1) complexity if random-access, else O(n) (even if bidirectional).

4 Likes

Rationale was provided under the "Alternatives Considered" section, as pointed out by:

Do you have any new findings in this area?

Terms of Service

Privacy Policy

Cookie Policy