[Review] SE-0065 A New Model for Collections and Indices

Evolution Announcements
21

Thanks for your comments, Brent!

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Some questions and comments:

    • Two for ranges that additionally conform to
RandomAccessCollection (requiring bounds that are Strideablewith
Stride conforming to Integer): CountableRange<T> and
CountableClosedRange<T>. These types can be folded into Range and
ClosedRange when Swift acquires conditional conformance capability.

Does this mean that once we have conditional conformances,
HalfOpenRangeProtocol and ClosedRangeProtocol will most likely go
away?

I'm not sure, honestly.

We also introduce three new protocols:

  • RangeProtocol
  • HalfOpenRangeProtocol
  • ClosedRangeProtocol

These protocols mostly exist facilitate implementation-sharing among
the range types, and would seldom need to be implemented outside the
standard library.

If these types are for implementation sharing, should they be
underscored to discourage their use? Or is the position they occupy in
the type hierarchy important because Range and ClosedRange will
eventually occupy them?

Underscoring hides names from users completely, and IMO that would not
be appropriate here. If we underscored them, it would be mysterious
where an implementation of various methods came from.

It seems to me that RangeProtocol is unlike the other two in that it's
a sensible thing to constrain a parameter to. Does the
"implementation-sharing" comment not really apply to it?

That could be argued either way, I think. One can't know for sure
without doing a redesign using a hypothetical more-capable Swift
language, which we don't have today.

On the other hand, it's not like the SubSequence subscript now takes a
RangeProtocol. Should it?

No; subscript can't be generic (language limitation).

(Has any thought been given to allowing you to close protocols to
outside conformances the way that resilience seems to suggest we'll
eventually allow you to close classes?)

I don't know who else might have thought about it, but personally I
don't think we want to do that.

• Two for general ranges (whose bounds are Comparable): Range<T> and
ClosedRange<T>. Having a separate ClosedRange type allows us to
address the vexing inability of the old Range to represent a range
containing the maximal value of its bound.

I notice that ClosedRange uses a ClosedRangeIndex to, essentially, add
one extra value for "larger than all values of this type". Could this
solution be applied to Range to allow us to unify Range and
ClosedRange, or are there other obstacles to that?

Performance is one such obstacle. Half-open ranges should be your go-to
range, and can be implemented more simply. There's also the problem of
how to decide whether the upper bound is part of the range. I'd rather
not have a dynamic check to select the comparison.

(There likely are. I just wanted to make sure the idea wasn't left unexplored.)

func successor(of i: Index) -> Index

Two things:

1. I would really like a version of this which returns Optional and is
guaranteed to go `nil` once it hits `endIndex`.

The primary question to answer when exploring this idea is, IMO, “what
does that do to the code in algorithms?” I can't imagine writing binary
search, partition, or rotate if I had to check for nil every time I
moved an index.

There can be a non-optional version too, or it might even be a feature
of the `index` family of methods instead of `successor` itself, but I
think it would be valuable to let the collection worry about the
bounds check.

Why would that be valuable?

It seems silly to check the index before calling `successor(of:)` when
`successor(of:)` is going to immediately perform the same check again
as a precondition.

Preconditions are not necessarily checked. We don't promise to trap
every precondition violation. We promise memory and type safety in the
absence of data races, and some precondition failures will trap in order
to ensure that. Others will trap, where we think it is affordable, just
to provide a better programmer experience.

(Actually, in general, I'm a little bit dismayed that the collection
API does so little to help you include bounds checks in your
code. Especially when iterating through a collection, bounds checks
are absolutely mandatory, and the collection API's solution to the
problem is "eh, just use `<`, it's not like you might mess something
like that up".)

What do you mean? Could you show an example of what you think should be
better supported?

2. There is a very strong parallel between this method and a
generator's `next()` method—the generator's `next()` calls
`successor(of:)` to get the index it should use—which makes me wonder
if this method should also be called `next(_:)` instead of
`successor(of:)`.

We had that in the code for a while. Certain people disliked it a lot.
Personally I think successor(of:) is still better, considering that
these methods end up getting thrown into the mix with all the other
methods on collections (e.g. sort()).

On the other hand, I have no good suggestion for a

func index(n: IndexDistance, stepsFrom i: Index) -> Index

Oof, I am really not a fan of this name. `steps` is sort-of a label on
the `n` parameter, but it's attached to `i`.

Yes, it's an awkward thing to name. Better suggestions most welcome.

Other collection APIs use `distance`, not `steps` (although "steps"
does appear in the documentation of the `Distance` associated
type). `index` puts it in a method family with `index(predicate:)` and
`index(of:)`, but those two are user-facing while this one is part of
the collection API. Even the word `index` itself is redundant with the
method return type.

I do understand how this is kind of parallel to `index(of:)` and
`index(predicate:)`, in that they all return an index calculated from
the parameters, but I think these methods are more different than they
are similar.

Compared to this:

  collection.index(5, stepsFrom: i)

I would prefer any of these (ordered from least favorite to most):

  collection.index(distance: 5, from: i)

I'm OK with this one, but am not sure it's an improvement over the
proposal. I'd like to hear other peoples' arguments on this.

  collection.index(5, from: i)

I don't think this one reads clearly enough.

  collection.traveling(5, from: i)
  collection.striding(5, from: i)
  collection.advancing(i, by: 5)

None of the “ing” names work, IMO because that suffix suggests you're
returning a modified version of the receiver.

A word on `striding(_:from:)` appearing in that list: Although
redesigning Strideable is not directly in scope for this proposal,
I've noticed that our discussions on modernizing Strideable seem to be
trending towards the idea that it operates on collections (or rather,
on an as-yet-unnamed supertype of `BidirectionalCollection` or
`RandomAccessCollection`) and strides by repeatedly calling a method
with the same semantics as this one. Thus, there seems to be an
intimate connection between this operation and Strideable. I think we
ought to choose a method name which suits that, and I don't think
`index` is it.

func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index

I have a few issues with this API.

1. As aforementioned, I'm not a big fan of using `index` as the base method name.

2. This method can move the index either forwards or backwards, but
only one limit is specified. Would we be better off having the `limit`
be a range?

That would add a cost for checking that one doesn't want to pay in
algorithms that need this method.

3. What is the use case for returning the `limit` instead of returning
the fact that we crossed it? I have a hard time thinking of a case
where I would want to just bump up against the limit and use it rather
than *detect* that I've hit the limit (which would probably call for a
return type of `Index?`). Are there common needs that I'm just not
thinking of?

Sure, for example

  x[i..<x.index(n, stepsFrom: i, limitedBy: x.endIndex)].sort()

Should we offer both?

Definitely not, IMO! They are utterly redundant, are they not?

···

on Sun Apr 10 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

  * What is your evaluation of the proposal?

Despite my criticisms, this is fundamentally a very good design. It
will not only improve the language, it will also open the door to
further improvements.

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

Yes. I believe this change is complicating in the short run but
actually simplifying in the long run, eliminating concepts like the
Index protocols which represented several overlapping semantics.

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

Yes.

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

Nothing with a collection design as rich as Swift's.

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

Somewhere between the latter two. I wouldn't call it in-depth when
it's such a big change, but I feel like I have too much background to
say it's a quick reading, either.

--
Dave

22

• Because Swift is unable to express conditional protocol

conformances, implementing this change has required us to create a
great deal of complexity in the standard library API. Aside from the
two excess “Countable” range types, there are new overloads for
slicing and twelve distinct slice types that capture all the
combinations of traversal, mutability, and range-replaceability. While
these costs are probably temporary, they are very real in the
meantime.

Is there a migration strategy possible for when we do support
conditional conformances?

Anything is possible ;-)

Would typealiasing the existing names to refinements of a more general
Slice<T> type be sufficient?

Maybe. It depends on your goals. *Some* code will break no matter what
we do.

···

on Mon Apr 11 2016, Joe Groff <swift-evolution@swift.org> wrote:

--
Dave

23

Thank you Dmitri!

···

Le 11 avr. 2016 à 18:22, Dmitri Gribenko <gribozavr@gmail.com> a écrit :

On Mon, Apr 11, 2016 at 9:20 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
Hi,

On Mon, Apr 11, 2016 at 9:16 AM, Gwendal Roué <swift-evolution@swift.org> wrote:
Will it still be possible with the new protocol and types? Especially, how to I generate "BETWEEN 0 AND 17" from 0..<18 without a supporting collection that gives me the predecessor of 18?

You would either design your API to accept a CountableRange, or a
Range where Bound conforms to Strideable.

You could also make your API generic over RangeProtocol where Bound
conforms to Strideable, check if the end point is contained in the
range (detecting closed ranges), and if it is not, perform the
adjustment.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

24

Aside: `indices` being irregular can be a benefit in the context of
auto-complete.

    * What is your evaluation of the proposal?

+1, very much.

As a change from the current model, it’s an across-the-board improvement for me,
at least.

In a bigger-picture sense I think Swift would be better off by going *further*
on certain aspects, but have said all that before.

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

It is, again very much so.

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

Depends on the framing of the question.

Compared to the previous model, it’s an unqualified YES.

As a general proposition, I think this design is a local optimum for overall
Swift-ness, but even so it’s creating a little un-Swifty pocket. It’s
“un-Swifty” in at least two ways:

# 1: Relatively Unsafe, Pointer-Like Semantics

Indices—unsurprisingly!—behave quite a bit like pointers, and similarly expose
*numerous* crashing combinations of `(value,operation)`:

- self[endIndex]
- self[startIndex] // <- when empty
- successor(of: endIndex)
- predecessor(of: startIndex)

…etc., which is *very much* reminiscent of the hazards of pointers. (Technically
“undefined” not “crashing”, but being realistic “crashing" is usually accurate).

No, these are unspecified in the general case, not undefined. Unless
you're working with, e.g. `UnsafeMutableBufferPointer` (or you have a
data race), there's no undefined behavior. The big problem with
pointers isn't what happens when they crash; it's what happens when they
*don't*.

Although Swift uses `Optional` to mitigate the hazards of `nil` pointers (etc.),
you’re still left to your own devices for handling indices.

`Optional` is not “mitigating hazards;” it's encoding the possibility of
null in the type system. It's non-optional things that mitigate hazards.

This isn’t news to anyone here, I’m sure, and may even be unavoidable; I’m just
pointing it out as an uncharacteristically-unsafe area in Swift’s standard APIs,
and closer to how `!` and IOUs behave than otherwise typical.

Any time there's a required relationship between two things, e.g. a
receiver and an argument, you have a precondition. The existence of a
precondition does not make something unsafe at all in the sense that
Swift uses the term. Safety in swift is about type and memory safety in
the absence of data races, not about having APIs that respond sensibly
to every possible combination of arguments. Int.max + 1 will trap, but
that doesn't make addition unsafe.

Saying that it's close to how `!` behaves is not at all far from the
truth, because `!` has a precondition that its argument is non-nil.

To help illustrate the claim, here’s a strawman “safe” API—for illustration
only, not advocacy!—that would be safer and thus perhaps more “Swift-y”:

I think there's a prevalent misunderstanding (IOW, I don't mean to
single out this post or this poster) about what “safe” means in Swift
and what the features of a Swifty API are and should be. This
is a big topic worthy of much more time than I can devote here, but
here's a thought to start with:

A Swifty API helps you reason effectively about the correctness of your
code, and in part that means we provide enough preconditions on
arguments to avoid complicating result types, and code to handle
results, with optional-ness.

···

on Tue Apr 12 2016, plx <swift-evolution@swift.org> wrote:

--
Dave

25

Thanks for your review, Tony!

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under
review through constructive criticism and, eventually, determine the
direction of Swift. When writing your review, here are some
questions you might want to answer in your review:

  * What is your evaluation of the proposal?

I agree with the general direction and scope of the proposal, but I
think the names could use some changes. Specifically, I don’t think
the fallback to ‘form’ is required.

It's not a fallback whatsoever. The updated guidelines referenced from

(which was accepted this morning; announcement forthcoming) make the
“form” prefix a first-class citizen that one chooses based on the
noun-ness of the underlying operation. Furthermore, *treating*
“formXXX” as a fallback and avoiding it will continue to strengthen the
sense that it's not something we should normally use, leading to more
naming arguments in the future. It's a strong guideline and as long as
we have it, we shouldn't be afraid to apply it, thereby increasing
uniformity and predictability.

[To all my fellow “InPlace” lovers out there: yes, another guideline
might be more optimal, but this is the guideline we have/can get].

It would be a significant readability improvement to use a meaningful
verb to describe the action of altering the argument. The methods that
create new indices probably need a label on the first argument,
because otherwise it looks as if the IndexDistance is what is
described by ‘index’.

Proposed:

  func successor(of i: Index) -> Index
  func formSuccessor(i: inout Index)

Instead, I suggest:

  func successor(of i : Index) -> Index
  func advance(i: inout Index)

Why is that an improvement? It loses the correspondence between the
operations, which are still a mutating/nonmutating pair. What's it got
to recommend it? I have the same question about all of the suggestions
below.

Proposed:

  func index(n: IndexDistance, stepsFrom i: Index) -> Index
  func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index
  func formIndex(n: IndexDistance, stepsFrom i: inout Index)
  func formIndex(n: IndexDistance, stepsFrom i: inout Index, limitedBy limit: Index)

Suggested (taking into account Nate’s suggestion of reversing the order):

  func index(startingAt i: Index, movedBy n: IndexDistance) -> Index
  func index(startingAt i: Index, movedBy n: IndexDistance, limitedBy limit: Index) -> Index

I find Nate Cook's concerns about the use of “index” here (a mental
clash with unrelated methods having the same basename) especially
convincing. So I think I want to look for other names for these.

  func move(i : inout Index, by n: IndexDistance)
  func move(i : inout Index, by n: IndexDistance, limitedBy limit: Index)

Proposed:

  func predecessor(of i: Index) -> Index
  func formPredecessor(i: inout Index)

Suggested:

  func predecessor(of i: Index) -> Index
  func reverse(i: inout Index)

I think reversing an index has some nice symmetry with reversing a
sequence, but if it seems to confusing, then replace advance and
reverse with ‘moveForward’ and ‘moveBackward’.

Yeah, I don't think moving an index one step backwards could reasonably
be called “reversing” it. “moveBackward” is reasonable, if one wanted
have to break the relationship with predecessor.

···

on Mon Apr 11 2016, Tony Parker <swift-evolution@swift.org> wrote:

On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

- Tony

  * 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 you 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?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

26

I’m a +1 for the proposal (but as I’ve implemented a bunch of collections recently I’m not sure I’m looking forward to having to update my code to reflect the new pattern ;)

But I’m interested by these concerns:

···

On 12 Apr 2016, at 17:57, plx via swift-evolution <swift-evolution@swift.org> wrote:

# 1: Relatively Unsafe, Pointer-Like Semantics
# 2: Index Invalidation Unrepresented In Type System

It seems to me as though we could solve #1 by solving #2 actually; if we knew when indices were invalid, then unless we’re storing .endIndex or using .startIndex or .endIndex on an empty collection (rather than .first and .last) then there should no issues of the safety of these “pointers" anymore.

The tricky thing is how to handle #2; we can do this at run-time by having indices include a reference to their parent (or some kind of ID class), plus a copy of a state variable which the collection will use to track invalidating changes. If an index is passed to the collection with an incorrect reference then it wasn’t for that collection, and if the states don’t match then the index was invalidated. But really it’d be better if we had some way to do this at compile-time which I think is what you meant; i.e- some way for the compiler to track when an index was invalidated between being stored and being used, so that passing it into the subscript or other methods will produce a warning.

I suppose this could be done using attributes on the return values for index generating properties/methods to assign some kind of tag which other methods can then mark as having been invalidated, so that anything assigned that tag can be considered invalid by the compiler if you try to use a value stored before the invalidation. This is something that could be done afterwards I think, so hopefully shouldn’t affect the proposal itself. There’ll be limits to how far the compiler can track this though, but it could help to avoid most of the simpler mistakes at least.

It’d be interesting if the compiler would also trace that an index belongs to a collection, to prevent you accidentally using compatible ones with the wrong collection when you have several; it’s good practice to check this with preconditions, or assertions for performance, but the compiler doing it could give more useful errors/advice.

27

The final revisions are reflected in the latest version of the
proposal:

Summary:

* We decided to take Shawn Erickson's excellent suggestion
  <http://article.gmane.org/gmane.comp.lang.swift.evolution/14450&gt; to
  use “location” uniformly for index movement, so instead of
  successor(i) and predecessor(i) we have location(after: i) and
  location(before: i).

* Since Brent Royal-Gordon pointed out
  <http://news.gmane.org/find-root.php?message_id=156D8FB1-1FD3-448E-8C70-6E7400629BC0%40architechies.com&gt;
  that two of the three proposed Range protocols would likely disappear
  in future updates, we took another look at all of them. Finding
  `RangeProtocol` itself to be a very weak abstraction, we removed all
  three from the proposal.

For those interested in details, implementation work proceeds apace on
the swift-3-indexing-model branch at
<https://github.com/apple/swift/tree/swift-3-indexing-model/stdlib/public/core&gt;\.

P.S. If anyone is interested in contributing, there are still plenty of
FIXMEs left for us to handle ;-)

···

on Wed Apr 20 2016, Chris Lattner <swift-evolution@swift.org> wrote:

On Apr 10, 2016, at 2:41 PM, Chris Lattner > <clattner@apple.com> wrote:

    Hello Swift community,

    The review of "A New Model for Collections and Indices" begins now and runs
    through April 18th. The proposal is available here:

    https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

    Reviews are an important part of the Swift evolution process. All reviews
    should be sent to the swift-evolution mailing list at:
    https://lists.swift.org/mailman/listinfo/swift-evolution
    or, if you would like to keep your feedback private, directly to the review
    manager.

A quick update: the core team met to discuss this. They agreed to accept it with
some naming-related revisions to the proposal (in response to community
feedback). Dave is organizing this feedback, and I’ll send out the formal
announcement when that is ready.

--
Dave

28

So, just confirming that the following is going to change:

—————
var string = "test"
let origLen = 4
let indexOne = string.startIndex

string.appendContentsOf("ANOTHERTEST")

let indexTwo = indexOne.advancedBy(origLen, limit: string.endIndex)

assert(indexTwo<string.endIndex)
indexTwo.successor() //<--- fatal error: cannot increment endIndex
—————

Hi Karl,

Yes, this code would start working.

Is this a consequence of the index needing to know its originating string for successor() purposes?

That would be a plausible explanation, but I think that would be too
simple to be true :) This code should even work in the current model,
but the current (buggy) behavior is caused by String indices keeping
an extra strong reference to the underlying storage, so the mutation
actually detaches the index from the updated string storage.

Once this is implemented, will String.Index be portable across string instances (presuming you bounds-check them, as I did above)?

Yes, within the prefix that was common to all strings and was created
in a common mutation history.

Dmitri

···

On Mon, May 2, 2016 at 3:08 PM, Karl via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

29

Minor questions after initial read-through:

- Should the comment on {index,formIndex}(_:stepsFrom:) say what happens if
the resulting index would be out of bounds?

Yes, we should make that clear. The answer is that you get
unspecified memory-safe behavior. We encourage implementations to
trap, but it is allowed to return an index that is invalid, and some
later use of it will trap, or return a valid index (say, equivalent to
startIndex).

Can these functions return
Optional values, or can they be `throws`?

Detecting such misuse can be too expensive, so it is not possible to
require these functions return a guaranteed indicator of failure.
Also, in most cases, producing an out-of-bounds index is a program
error, and it is not possible to recover from it. (Imagine that you
are writing sort(), and you need to split the collection in two halves
-- what would you do if index() returns nil?)

- Can {index,formIndex}(_:stepsFrom:) be combined with the limitedBy:
versions, such that the limit is an optional parameter with default value
nil? For example:

    public func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit:
Index? = nil)

We considered it, but decided against it. This function is a
requirement of RandomAccessCollection. The two-argument form is
usually trivial to implement. The three-argument form is very tricky
to implement correctly for all edge cases. So we require the
two-argument form, and provide a default implementation for the
three-argument one.

Dmitri

···

On Sun, Apr 10, 2016 at 4:16 PM, Jacob Bandes-Storch via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

30

Joe’s isn’t saying that “Indexes” is more common, rather that it’s regular (i.e. follows the usual declension rule for plurals); there’s tradeoffs each way, but using the regular plural might make it more familiar for some non-native speakers/readers.

– Steve

···

On Apr 11, 2016, at 9:42 AM, Trent Nadeau via swift-evolution <swift-evolution@swift.org> wrote:

I disagree. According to both Indexes or Indices – The Plural Debate and World Wide Words: Indexes versus indices, "indices" is more common in the English-speaking world (outside of parts of America and Canada) as well as in technical contexts.

On Mon, Apr 11, 2016 at 12:29 PM, Joe Groff via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
I love irregular plurals as much as the next grammar nerd, but I think it'd be better to use the more regular, but still correct, plural "indexes" rather than "indices".

-Joe

> On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> Hello Swift community,
>
> The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:
>
> https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
>
> Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
> https://lists.swift.org/mailman/listinfo/swift-evolution
> or, if you would like to keep your feedback private, directly to the review manager.
>
>
> What goes into a review?
>
> The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:
>
> * 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 you 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?
>
> More information about the Swift evolution process is available at
>
> https://github.com/apple/swift-evolution/blob/master/process.md
>
> Thank you,
>
> -Chris Lattner
> Review Manager
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Trent Nadeau
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

31

Yeah. From personal experience I've worked with many developers for whom "indices" was an unfamiliar term, whereas "indexes" was immediately obvious.

-Joe

···

On Apr 11, 2016, at 9:48 AM, Stephen Canon <scanon@apple.com> wrote:

Joe’s isn’t saying that “Indexes” is more common, rather that it’s regular (i.e. follows the usual declension rule for plurals); there’s tradeoffs each way, but using the regular plural might make it more familiar for some non-native speakers/readers.

32

Minor questions after initial read-through:

- Should the comment on {index,formIndex}(_:stepsFrom:) say what happens if the
resulting index would be out of bounds?

I don't think we should ever specify what happens when preconditions are
violated. That brings into question how to evaluate the correctness of
a program. If the behavior is specified, the program has every right to
depend on that behavior, and then it's meaningless to say “you violated a
precondition, so the program is broken.”

Can these functions return Optional values, or can they be `throws`?

No, precondition violations should never be treated as conditions from
which execution can continue.

- Can {index,formIndex}(_:stepsFrom:) be combined with the limitedBy: versions,
such that the limit is an optional parameter with default value nil? For
example:

No, due to language limitations: you can't put default arguments in
protocol requirements.

···

on Sun Apr 10 2016, Jacob Bandes-Storch <swift-evolution@swift.org> wrote:

public func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index?
= nil)

Jacob

On Sun, Apr 10, 2016 at 2:45 PM, Chris Lattner via swift-evolution > <swift-evolution@swift.org> wrote:

        On Apr 10, 2016, at 2:41 PM, Chris Lattner > <clattner@apple.com> wrote:

        Hello Swift community,

        The review of "A New Model for Collections and Indices" begins now and
        runs through April 18th. The proposal is available here:

    The correct link is:
    https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

    -Chris

        Reviews are an important part of the Swift evolution process. All
        reviews should be sent to the swift-evolution mailing list at:
        https://lists.swift.org/mailman/listinfo/swift-evolution
        or, if you would like to keep your feedback private, directly to the
        review manager.

        What goes into a review?

        The goal of the review process is to improve the proposal under review
        through constructive criticism and, eventually, determine the direction
        of Swift. When writing your review, here are some questions you might
        want to answer in your review:

        * 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 you 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?

        More information about the Swift evolution process is available at

        https://github.com/apple/swift-evolution/blob/master/process.md

        Thank you,

        -Chris Lattner
        Review Manager

    _______________________________________________
    swift-evolution mailing list
    swift-evolution@swift.org
    https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

33

At least in my experience, "indices" is used throughout technical
documentation and code, such as the official docs of Python, Java, and C#.

I'm not strongly opposed to "indexes", but I think there should be a
stronger reason to change it other than that it has easier discoverability
for non-English speakers (who can search for it in a few seconds). I think
of "indices" as a term of art or a word in a technical dialect of English.

···

On Mon, Apr 11, 2016 at 12:49 PM, Joe Groff <jgroff@apple.com> wrote:

> On Apr 11, 2016, at 9:48 AM, Stephen Canon <scanon@apple.com> wrote:
>
> Joe’s isn’t saying that “Indexes” is more common, rather that it’s
regular (i.e. follows the usual declension rule for plurals); there’s
tradeoffs each way, but using the regular plural might make it more
familiar for some non-native speakers/readers.

Yeah. From personal experience I've worked with many developers for whom
"indices" was an unfamiliar term, whereas "indexes" was immediately obvious.

-Joe

--
Trent Nadeau

34

Joe’s isn’t saying that “Indexes” is more common, rather that it’s regular (i.e.
follows the usual declension rule for plurals); there’s tradeoffs each way, but
using the regular plural might make it more familiar for some non-native
speakers/readers.

Indexes also has the disadvantage of being a verb as well as a plural noun.

···

on Mon Apr 11 2016, Stephen Canon <swift-evolution@swift.org> wrote:

– Steve

    On Apr 11, 2016, at 9:42 AM, Trent Nadeau via swift-evolution > <swift-evolution@swift.org> wrote:

    I disagree. According to both http://grammarist.com/usage/indexes-indices/
    and http://www.worldwidewords.org/qa/qa-ind2.htm, "indices" is more common
    in the English-speaking world (outside of parts of America and Canada) as
    well as in technical contexts.

    On Mon, Apr 11, 2016 at 12:29 PM, Joe Groff via swift-evolution > <swift-evolution@swift.org> wrote:

    I love irregular plurals as much as the next grammar nerd, but I think it'd
        be better to use the more regular, but still correct, plural "indexes"
        rather than "indices".

        -Joe

        > On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution > <swift-evolution@swift.org> wrote:
        >
        > Hello Swift community,
        >
        > The review of "A New Model for Collections and Indices" begins now and
        runs through April 18th. The proposal is available here:
        >
        >
        https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

        >
        > Reviews are an important part of the Swift evolution process. All
        reviews should be sent to the swift-evolution mailing list at:
        > https://lists.swift.org/mailman/listinfo/swift-evolution
        > or, if you would like to keep your feedback private, directly to the
        review manager.
        >
        >
        > What goes into a review?
        >
        > The goal of the review process is to improve the proposal under review
        through constructive criticism and, eventually, determine the direction
        of Swift. When writing your review, here are some questions you might
        want to answer in your review:
        >
        > * 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 you 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?
        >
        > More information about the Swift evolution process is available at
        >
        > https://github.com/apple/swift-evolution/blob/master/process.md
        >
        > Thank you,
        >
        > -Chris Lattner
        > Review Manager
        >
        >

        > _______________________________________________
        > swift-evolution mailing list
        > swift-evolution@swift.org
        > https://lists.swift.org/mailman/listinfo/swift-evolution

        _______________________________________________
        swift-evolution mailing list
        swift-evolution@swift.org
        https://lists.swift.org/mailman/listinfo/swift-evolution

    --

    Trent Nadeau
    _______________________________________________
    swift-evolution mailing list
    swift-evolution@swift.org
    https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

35

Reconsidering, they aren't used anywhere else in the standard library so
I'd say that is indeed likely. In fact, something I'm working on at the
moment may make it happen sooner than that ;-). Stay tuned.

···

on Mon Apr 11 2016, Dave Abrahams <swift-evolution@swift.org> wrote:

Thanks for your comments, Brent!

on Sun Apr 10 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Some questions and comments:

    • Two for ranges that additionally conform to
RandomAccessCollection (requiring bounds that are Strideablewith
Stride conforming to Integer): CountableRange<T> and
CountableClosedRange<T>. These types can be folded into Range and
ClosedRange when Swift acquires conditional conformance capability.

Does this mean that once we have conditional conformances,
HalfOpenRangeProtocol and ClosedRangeProtocol will most likely go
away?

I'm not sure, honestly.

--
Dave

36

Just to throwing out some additional ideas...

"index moved x steps from i"
index = collection.index(moved: 5, stepsFrom: i)
index = collection.index(moved: -10, stepsFrom: i)

"index offset x from i"
index = collection.index(offset: 5, from: i)
index = collection.index(offset: -10, from: i)

"index advanced x from i"
index = collection.index(advanced: 5, from: i)
index = collection.index(advanced: -10, from: i)

...of course also start to wonder why not the following...

"index after/before i"
index = collection.index(after:i)
index = collection.index(before:i)

...instead of the separately name styled successor / predecessor functions.

I am still hesitant about the use of "form" for in the in place variants,
throwing out more ideas, of course these break from the "index" style
naming above but on could argue the above naming is attempting to imply you
get a new index back while the following are attempting to avoid that.

"move index i by x"
collection.move(index: i, by: 5)
collection.offest(index: i, by: -3)

"offset index i by x"
collection.offest(index: i, by: 5)
collection.offest(index: i, by: -3)

"advance index i by x"
collection.advance(index: i, by: 5)
collection.advance(index: i, by: -3)

I think I like the ones using advance the best and if the "index(" ones are
the path forward I would lobby for index(after:)/index(before:) instead of
successor and predecessor.

-Shawn

···

On Mon, Apr 11, 2016 at 1:01 PM Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

> Compared to this:
>
> collection.index(5, stepsFrom: i)
>
> I would prefer any of these (ordered from least favorite to most):
>
> collection.index(distance: 5, from: i)

I'm OK with this one, but am not sure it's an improvement over the
proposal. I'd like to hear other peoples' arguments on this.

37

Proposal link: https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Thanks for your comments, Brent!

The shift described in this proposal is extremely valuable and makes implementing collections far more intuitive, as all the collection's logic lives "inside" the collection itself. My only hesitation is with the naming of the method that Brent also called out:

... snip ...

func index(n: IndexDistance, stepsFrom i: Index) -> Index

Oof, I am really not a fan of this name. `steps` is sort-of a label on
the `n` parameter, but it's attached to `i`.

Oof indeed! This is a very unusual method in the standard library, since we're calling on one instance to perform an action on another. My problems with the naming are twofold:

(1) Collision with the index(of:) and index(where:) APIs
The existing methods are used for searching a collection, possibly finding a matching index, possibly not. The new ones deterministically find an new index at a prescribed distance, with important and slightly complicated preconditions. These differences make the use and "flavor" of the two sets of methods distinct enough that I think they should have different names.

(2) Arguments are reversed
I think the ideal API for this would be index.advanced(by: 5, in: c), but I prefer keeping the index-moving implementation in the collection, not the index. I would favor any naming for this method that puts the index before the distance, keeping the overall shape of the advanced(by:) method. c.advance(i, by: 4) would be my pick.

....and finally I'll just go ahead and say again that I prefer -InPlace over form-. That's all, I'm done!

Nate

ps. Seriously, collections make so much more sense with this change. +1000

···

On Apr 11, 2016, at 2:59 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Sun Apr 10 2016, Brent Royal-Gordon <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Yes, it's an awkward thing to name. Better suggestions most welcome.

Other collection APIs use `distance`, not `steps` (although "steps"
does appear in the documentation of the `Distance` associated
type). `index` puts it in a method family with `index(predicate:)` and
`index(of:)`, but those two are user-facing while this one is part of
the collection API. Even the word `index` itself is redundant with the
method return type.

I do understand how this is kind of parallel to `index(of:)` and
`index(predicate:)`, in that they all return an index calculated from
the parameters, but I think these methods are more different than they
are similar.

Compared to this:

  collection.index(5, stepsFrom: i)

I would prefer any of these (ordered from least favorite to most):

  collection.index(distance: 5, from: i)

I'm OK with this one, but am not sure it's an improvement over the
proposal. I'd like to hear other peoples' arguments on this.

  collection.index(5, from: i)

I don't think this one reads clearly enough.

  collection.traveling(5, from: i)
  collection.striding(5, from: i)
  collection.advancing(i, by: 5)

None of the “ing” names work, IMO because that suffix suggests you're
returning a modified version of the receiver.

A word on `striding(_:from:)` appearing in that list: Although
redesigning Strideable is not directly in scope for this proposal,
I've noticed that our discussions on modernizing Strideable seem to be
trending towards the idea that it operates on collections (or rather,
on an as-yet-unnamed supertype of `BidirectionalCollection` or
`RandomAccessCollection`) and strides by repeatedly calling a method
with the same semantics as this one. Thus, there seems to be an
intimate connection between this operation and Strideable. I think we
ought to choose a method name which suits that, and I don't think
`index` is it.

func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index

I have a few issues with this API.

1. As aforementioned, I'm not a big fan of using `index` as the base method name.

2. This method can move the index either forwards or backwards, but
only one limit is specified. Would we be better off having the `limit`
be a range?

That would add a cost for checking that one doesn't want to pay in
algorithms that need this method.

3. What is the use case for returning the `limit` instead of returning
the fact that we crossed it? I have a hard time thinking of a case
where I would want to just bump up against the limit and use it rather
than *detect* that I've hit the limit (which would probably call for a
return type of `Index?`). Are there common needs that I'm just not
thinking of?

Sure, for example

x[i..<x.index(n, stepsFrom: i, limitedBy: x.endIndex)].sort()

Should we offer both?

Definitely not, IMO! They are utterly redundant, are they not?

  * What is your evaluation of the proposal?

Despite my criticisms, this is fundamentally a very good design. It
will not only improve the language, it will also open the door to
further improvements.

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

Yes. I believe this change is complicating in the short run but
actually simplifying in the long run, eliminating concepts like the
Index protocols which represented several overlapping semantics.

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

Yes.

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

Nothing with a collection design as rich as Swift's.

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

Somewhere between the latter two. I wouldn't call it in-depth when
it's such a big change, but I feel like I have too much background to
say it's a quick reading, either.

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

38

If these types are for implementation sharing, should they be
underscored to discourage their use? Or is the position they occupy in
the type hierarchy important because Range and ClosedRange will
eventually occupy them?

Underscoring hides names from users completely, and IMO that would not
be appropriate here. If we underscored them, it would be mysterious
where an implementation of various methods came from.

If the concrete types show these members, does it matter that they actually came from a protocol?

On the other hand, it's not like the SubSequence subscript now takes a
RangeProtocol. Should it?

No; subscript can't be generic (language limitation).

Right, and RangeProtocol isn't existential. Ouch.

func successor(of i: Index) -> Index

Two things:

1. I would really like a version of this which returns Optional and is
guaranteed to go `nil` once it hits `endIndex`.

The primary question to answer when exploring this idea is, IMO, “what
does that do to the code in algorithms?” I can't imagine writing binary
search, partition, or rotate if I had to check for nil every time I
moved an index.

If you're confident you're remaining in bounds, you should force-unwrap it.

There can be a non-optional version too, or it might even be a feature
of the `index` family of methods instead of `successor` itself, but I
think it would be valuable to let the collection worry about the
bounds check.

Why would that be valuable?

It seems silly to check the index before calling `successor(of:)` when
`successor(of:)` is going to immediately perform the same check again
as a precondition.

Preconditions are not necessarily checked. We don't promise to trap
every precondition violation. We promise memory and type safety in the
absence of data races, and some precondition failures will trap in order
to ensure that. Others will trap, where we think it is affordable, just
to provide a better programmer experience.

I understand that, but many—perhaps most—clients of APIs like `successor(of:)` will need to perform a bounds check. I think we would be better off if the check were implicit in the call. That would force all clients, or at least all clients which used the bounds-checking variants (which would be encouraged), to explicitly handle out-of-bounds conditions, in much the same way that `index(of:)` forces its clients to explicitly handle the possibility that a matching element might not exist, rather than returning `endIndex` (which would be easier).

(Actually, in general, I'm a little bit dismayed that the collection
API does so little to help you include bounds checks in your
code. Especially when iterating through a collection, bounds checks
are absolutely mandatory, and the collection API's solution to the
problem is "eh, just use `<`, it's not like you might mess something
like that up".)

What do you mean? Could you show an example of what you think should be
better supported?

The simplest thing would simply be to have calls like these in Collection:

  func validate(i: Index) -> Bool
  func validateIncreasing(i: Index) -> Bool
  func validateDecreasing(i: Index) -> Bool

Usage:

  while collection.validateIncreasing(i) {
    collection[i] = repeatedValue
    i = collection.successor(of: i)
  }

These methods would be one-liners, sure, but they would make your code say what was *meant*, not what happened to be true.

However, we could go further than this and perhaps reduce the amount of bounds-checking we do, even across optimization barriers.

To explain what I mean, let's take a look at `IndexingIterator`. With various less-interesting bits stripped out, the pull request defines it like this:

  public struct IndexingIterator<Elements: IndexableBase>: IteratorProtocol, Sequence {
    init(_elements: Elements) {
      self._elements = _elements
      self._position = _elements.startIndex
    }

    mutating func next() -> Elements._Element? {
      if _position == _elements.endIndex { return nil }
      let element = _elements[_position]
      _elements.formSuccessor(&_position)
      return element
    }

    internal let _elements: Elements
    internal var _position: Elements.Index
  }

Let's annotate the `next()` method with its bounds-checking behavior.

    mutating func next() -> Elements._Element? {
      if _position == _elements.endIndex { return nil } // Explicit bounds check performed here
      let element = _elements[_position] // Usually precondition()s a bounds check to preserve memory safety
      _elements.formSuccessor(&_position) // May perform a bounds check on the incremented value
      return element
    }

Depending on the implementation, at least two, and possibly all three, of these lines will involve a bounds check. Now, perhaps the optimizer is good at eliding redundant checks involving an IndexingIterator because stdlib is transparent, but similar user code wouldn't get that benefit.

So, imagine that we have a type like this in the standard library:

  /// Represents a pre-validated index. A pre-validated index received from a given collection is
  /// guaranteed to refer to a valid element in that collection, as long as the collection is not mutated.
  ///
  /// -Warning: Operations which accept a Valid<Index> assume it is in bounds and do not perform
  /// bounds checks. Using a Valid<Index> on a collection other than the one which created
  /// it, or on a collection which has been mutated since it was created, may be unsafe.
  struct Valid<Index: Comparable> {
    init(unsafeIndex index: Index) { self.index = index }
    private(set) var index: Index
  }

And a few members like these in the Collection protocols (there would be others; I'm just defining the ones we're using here:

  /// Validates an index, returning `nil` if it is invalid, or a Valid<Index> for that index otherwise.
  func validate(i: Index) -> Valid<Index>?
  
  /// Transforms `i` to represent the next valid index after itself, or `nil` if that index would be out of bounds.
  func formValidSuccessor(i: inout Valid<Index>?)
  
  /// Accesses the element corresponding to the prevalidated index
  subscript (i: Valid<Index>) -> Element { get }

With those in hand, you can rewrite IndexingIterator like so:

  public struct IndexingIterator<Elements: IndexableBase>: IteratorProtocol, Sequence {
    init(_elements: Elements) {
      self._elements = _elements
      self._position = _elements.validate(_elements.startIndex)
    }

    mutating func next() -> Elements._Element? {
      if _position == nil { return nil } // This merely checks the result of the previous bounds check
      let element = _elements[_position!] // No bounds check needed
      _elements.formValidSuccessor(&_position!) // This is the only bounds check in the loop
      return element
    }

    internal let _elements: Elements
    internal var _position: Valid<Elements.Index>?
  }

This version only tests the bounds once per element, inside `formValidSuccessor(_:)` (or in `validate` for the start index), rather than several times.

(Incidentally, `Valid<Int>?` could theoretically be expressed in the size of a normal `Int`, since `endIndex <= Int.max`, and `endIndex` is not valid. I don't see a good way to tell Swift about this, though.)

  collection.index(5, from: i)

I don't think this one reads clearly enough.

"The index 5 from i" reads fine to me, but I guess that's a matter of opinion.

  collection.traveling(5, from: i)
  collection.striding(5, from: i)
  collection.advancing(i, by: 5)

None of the “ing” names work, IMO because that suffix suggests you're
returning a modified version of the receiver.

Huh, that clarifies something. How about the non-`ing` variants?

  collection.travel(5, from: i)
  collection.stride(5, from: i)
  collection.advance(i, by: 5)

I'd say `stride` might be an attractive nuisance in this form (although if Strideable's public face becomes `Self.striding(by:)`, only to Swift 2 users) but the others look fine to me.

func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index

2. This method can move the index either forwards or backwards, but
only one limit is specified. Would we be better off having the `limit`
be a range?

That would add a cost for checking that one doesn't want to pay in
algorithms that need this method.

I'm a little uncomfortable with the way `limit`'s interpretation changes based on the sign of `n` here; a stray arithmetic error could turn a maximum into a minimum, with potentially bizarre results. In the code, it looks like we end up branching to accommodate that interpretation, too, which isn't ideal.

I might feel a little better with a variant for each limit semantic:

  func index(n: IndexDistance, stepsFrom: Index, belowLimit: Index) -> Index // for when you expect to move up
  func index(n: IndexDistance, stepsFrom: Index, aboveLimit: Index) -> Index // for when you expect to move down
  func index(n: IndexDistance, stepsFrom: Index, withinLimits: Range<Index>) -> Index // for when you don't know which direction you're going

3. What is the use case for returning the `limit` instead of returning
the fact that we crossed it? I have a hard time thinking of a case
where I would want to just bump up against the limit and use it rather
than *detect* that I've hit the limit (which would probably call for a
return type of `Index?`). Are there common needs that I'm just not
thinking of?

Sure, for example

x[i..<x.index(n, stepsFrom: i, limitedBy: x.endIndex)].sort()

Let me restate that. Given that Swift doesn't usually seem to truncate ranges that are too long (though there are exceptions), are we more frequently going to want to stop at the limit, or to detect that the limit has been hit?

Should we offer both?

Definitely not, IMO! They are utterly redundant, are they not?

Well, an Optional-returning `index(_:stepsFrom:limitedBy:)` can be treated as a truncating version pretty easily. For instance, `prefix(_:)` can do this:

  let end = index(numericCast(maxLength), stepsFrom: startIndex, limitedBy: endIndex) ?? endIndex
  return self[startIndex..<end]

This is a bit of a hassle, and might be less efficient (an optional return, an extra test), but I don't think you can reliably go in the other direction.

(On the other hand, it might be that I'm conceiving of the purpose of `limitedBy` differently from you—I think of it as a safety measure, but you may be thinking of it specifically as an automatic truncation mechanism.)

···

--
Brent Royal-Gordon
Architechies

39

Hi plx,

In case of RangeReplaceableCollection, the index invalidation rules
that we currently have in mind (but haven't documented in public
documentation yet) imply that your fast path is always correct.

Dmitri

···

On Tue, Apr 12, 2016 at 8:46 PM, plx via swift-evolution <swift-evolution@swift.org> wrote:

On Apr 12, 2016, at 6:11 PM, Haravikk <swift-evolution@haravikk.me> wrote:

I’m a +1 for the proposal (but as I’ve implemented a bunch of collections
recently I’m not sure I’m looking forward to having to update my code to
reflect the new pattern ;)

But I’m interested by these concerns:

On 12 Apr 2016, at 17:57, plx via swift-evolution > <swift-evolution@swift.org> wrote:

# 1: Relatively Unsafe, Pointer-Like Semantics
# 2: Index Invalidation Unrepresented In Type System

It seems to me as though we could solve #1 by solving #2 actually; if we
knew when indices were invalid, then unless we’re storing .endIndex or using
.startIndex or .endIndex on an empty collection (rather than .first and
.last) then there should no issues of the safety of these “pointers"
anymore.

FWIW I think “solving” invalidation in the sense of being able to detect
invalidity is useful, but what I’d personally be more interested in is e.g.
something like this:

  protocol Collection {

    // throw this into the definition:
    static var indexCharacteristics: IndexCharacteristics { get }

  }

  extension RangeReplaceableCollection {

    mutating func removeElementsFailing(@noescape predicate: (Element) ->
Bool) {
      if Self.indexCharacteristics.removalOnlyInvalidatesRightward() {
        // presumptive “fast path”, deleting “back-to-front” to
        // avoid making a copy. Just for sake of illustration!
        for index in self.indices.dropLast().reverse() where
!predicate(self[index]) {
          self.removeAtIndex(index)
        }
      } else {
        // presumptive “slow path”, we rebuild ourself with the failing
elements omitted
        self = Self(self.lazy.filter() { predicate($0) })
        // ^ assuming self-assignment allowed...
      }
    }

  }

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

40

I’m a +1 for the proposal (but as I’ve implemented a bunch of collections recently I’m not sure I’m looking forward to having to update my code to reflect the new pattern ;)

But I’m interested by these concerns:

# 1: Relatively Unsafe, Pointer-Like Semantics
# 2: Index Invalidation Unrepresented In Type System

It seems to me as though we could solve #1 by solving #2 actually; if we knew when indices were invalid, then unless we’re storing .endIndex or using .startIndex or .endIndex on an empty collection (rather than .first and .last) then there should no issues of the safety of these “pointers" anymore.

FWIW I think “solving” invalidation in the sense of being able to detect invalidity is useful, but what I’d personally be more interested in is e.g. something like this:

  protocol Collection {

    // throw this into the definition:
    static var indexCharacteristics: IndexCharacteristics { get }

  }
  
  extension RangeReplaceableCollection {

    mutating func removeElementsFailing(@noescape predicate: (Element) -> Bool) {
      if Self.indexCharacteristics.removalOnlyInvalidatesRightward() {
        // presumptive “fast path”, deleting “back-to-front” to
        // avoid making a copy. Just for sake of illustration!
        for index in self.indices.dropLast().reverse() where !predicate(self[index]) {
          self.removeAtIndex(index)
        }
      } else {
        // presumptive “slow path”, we rebuild ourself with the failing elements omitted
        self = Self(self.lazy.filter() { predicate($0) })
        // ^ assuming self-assignment allowed...
      }
    }
  
  }

…e.g. some way to get some kind of coarse-grained behavior-characterization of “what actions invalidate which indices”, thereby allowing one to know when various approaches will work.

Invalidation is hard and I wouldn’t want anything held up to try and find a solution first.

···

On Apr 12, 2016, at 6:11 PM, Haravikk <swift-evolution@haravikk.me> wrote:

On 12 Apr 2016, at 17:57, plx via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

The tricky thing is how to handle #2; we can do this at run-time by having indices include a reference to their parent (or some kind of ID class), plus a copy of a state variable which the collection will use to track invalidating changes. If an index is passed to the collection with an incorrect reference then it wasn’t for that collection, and if the states don’t match then the index was invalidated. But really it’d be better if we had some way to do this at compile-time which I think is what you meant; i.e- some way for the compiler to track when an index was invalidated between being stored and being used, so that passing it into the subscript or other methods will produce a warning.

I suppose this could be done using attributes on the return values for index generating properties/methods to assign some kind of tag which other methods can then mark as having been invalidated, so that anything assigned that tag can be considered invalid by the compiler if you try to use a value stored before the invalidation. This is something that could be done afterwards I think, so hopefully shouldn’t affect the proposal itself. There’ll be limits to how far the compiler can track this though, but it could help to avoid most of the simpler mistakes at least.

It’d be interesting if the compiler would also trace that an index belongs to a collection, to prevent you accidentally using compatible ones with the wrong collection when you have several; it’s good practice to check this with preconditions, or assertions for performance, but the compiler doing it could give more useful errors/advice.