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

[plx]

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...
     }
   }

}

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.

That’s good news!

Fact is, I only went with that because I was actually fishing around for the weakest generic collection protocol that supported removal, and that seems to be it.

It’d be a more compelling motivating example if it used, e.g.:

  // “fictional”, not in stdlib:
  protocol IndexDeletingCollection : Collection {

    mutating func removeAtIndex(i: Index) -> Generator.Element

  }

…since there’d then be a more realistic chance of having multiple “flavors” of invalidation to consider.

But I could certainly live with a setup wherein generally protocols typically required “compatible” invalidation semantics on their indices.

···

On Apr 12, 2016, at 10:53 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
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:
On 12 Apr 2016, at 17:57, plx via swift-evolution >> <swift-evolution@swift.org> wrote:

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>*/

[Tony_Parker]

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
https://github.com/apple/swift-evolution/blob/master/proposals/0059-updated-set-apis.md
(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].

In other cases, the mutating pair of methods refer to the receiver, not the argument.

x = y.union(z) // new value x
y.formUnion(z) // mutates y, not z

x = y.successor(z) // new value x
y.formSuccessor(z) // mutates z (or replaces), not y

I think using the form prefix here will confuse this case with the others, when they are meaningfully different.

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.

It’s an improvement because it is much easier to read and understand what it means. The phrase “form successor” only makes sense if you dive into the naming guidelines to see why we have the “form” prefix in the first place. Plus, as I said, the form prefix implies a mutation of the wrong argument.

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.

Reverse is the best opposite we have of advance, so it makes sense to me. Or we could use retreat. =) There are other pairs of words that work as well, like “increment/decrement”. It’s rather an implementation detail of the index and collection what exactly these do, but conceptually modeling them as increment and decrement would likely make intuitive sense to most CS 101 students.

The reason that advance/reverse and increment/decrement work better is because they are active words that describe what happens to the argument, which has no other label. “form” describes little about the action that is actually taken on the argument. Therefore, to me it feels like a placeholder or fallback.

- Tony

···

On Apr 12, 2016, at 3:43 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Mon Apr 11 2016, Tony Parker <swift-evolution@swift.org <mailto: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

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

[Haravikk3 (Haravikk)]

Oh I agree, that was partly my point though; while this proposal may leave us with the "un-Swifty" issue of being unable to explicitly handle invalidation, it should be possible to solve that later, i.e- this proposal does’t make us any more vulnerable to that problem than we are now, but I definitely agree that we could do with some kind of invalidation mechanism in future that developers can actually implement or respond to. I guess I was more thinking out loud about whether the problem affects the proposal or not, but I don’t think that solving it will place any restrictions on the API as proposed, definitely deserves a proposal of its own once the new indexing system is in place though!

···

On 13 Apr 2016, at 04:46, plx via swift-evolution <swift-evolution@swift.org> wrote:

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

[plx]

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.

I meant it as a much more exact analogy.

In a collections-move-indices world, you *could* handle indices as pointers have been handled, bringing in support from the type-system:

  enum SaferIndex<T:Comparable> {
    case Position(T)
    case End
  }

…(yes, this is more-or-less `Optional` by another name).

The assumption above is `T` would be today’s “Index” types, w/o the value used for `endIndex` (e.g. 0..<self.count for an array, the non-`endIndex` values of `DictionaryIndex` and `SetIndex`, and so on).

It would’ve been awkward to do this under the previous status quo—e.g. even for arrays your indices would have to have a back-reference to get the count, and thus couldn’t be plain integers—but the collection will now always be present to provide such info.

Cons:

- more overhead than “bare” indices
- doesn’t address invalidation (but what does, really?)

Pros:

- easier in some ways to handle things like e.g 0…Int.max
- the endIndex equivalent *never* invalidates
- compile-time help for end-index checking

Overall this *would* bring the treatment of indices closer to that for `?`—e.g., redefine the core type to omit the `nil`-like value, use an enum to reintroduce that value when necessary—than to `!`.

I don’t think the above is an *improvement* over the proposal, but it’s a route that could have been taken.

···

On Apr 12, 2016, at 5:25 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Tue Apr 12 2016, plx <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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.
--
Dave

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

[xwu (Xiaodi Wu)]

Quick thought:

Why are you reaching for the "form..." rule for the mutating methods when
there are clear verb counterparts?
location: locate
successor: succeed

···

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

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.

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

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

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
>
  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
>.

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

--
Dave

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

[Joe_Groff]

That thought did cross my mind, but I think the potential for verb/noun confusion seems pretty well handled by context. As a verb, "index" is most commonly transitive, so I'd expect 'foo.indexes' to be a property whose value produces indexes, and 'foo.indexes(...)', if it existed, to be some kind of predicate method.

-Joe

···

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

on Mon Apr 11 2016, Stephen Canon <swift-evolution@swift.org> 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.

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

[gribozavr (Dmitri Gribenko)]

Hi Brent,

Index invalidation rules are much more complex than what this model
can express. For example, Array's indices can become invalid after
you remove elements from it. Even if you have validated indices
around, that validation is now invalidated. Not even to mention that
indices are valid only in context of a particular collection instance,
so in this model you could validate an index against one collection
and use it with another one. Please read
https://github.com/apple/swift/blob/master/docs/IndexInvalidation.rst
for a more detailed description of the rules.

Dmitri

···

On Mon, Apr 11, 2016 at 9:56 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

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
        }

--
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>*/

[gribozavr (Dmitri Gribenko)]

Hi Brent,

Could you explain what kind of safety do you have in mind? Swift will
guarantee memory safety even if you attempt to advance an index past
endIndex using the non-limiting overload.

Dmitri

···

On Mon, Apr 11, 2016 at 9:56 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

(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.)

--
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>*/

[dabrahams (Dave Abrahams)]

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.

Yup, I think that's a strong argument.

(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.

Right, that would be great, except that it's a non-side-effectful method
and if we “noun the verb” (e.g. c.advanced(...)) it is now a method that
should return a modified version of the receiver, which it does not. In
other words, there's no path to a non-mutating variant of the method.
One other possible approach: make the only method mutating, so instead
of

    let j = c.index(5, stepsFrom: i)

you get:

    var j = i
    c.advance(&j, by: 5)
    // ...use j...

I think being forced to accept making j mutable would be a sad tradeoff
to make just because the name of the method makes us uncomfortable, but
it's an option.

....and finally I'll just go ahead and say again that I prefer -InPlace over
form-.

Yer preachin' to the choir, brother.

···

on Mon Apr 11 2016, Nate Cook <natecook-AT-gmail.com> wrote:

    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> wrote:

That's all, I'm done!

Nate

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

    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
    https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

[dabrahams (Dave Abrahams)]

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?

I don't know; would the concrete types show these members?

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.

s/check for nil/force unwrap/

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.

Why do you say so?

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).

I think we agree that the proposed index method that takes a limit
should return optional. Dmitri's going to explain more in his response.

  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)

Active verb phrases are reserved for methods with side-effects according
to the API guidelines.

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.

I'm going to leave the rest of this for Dmitri, at least for the time
being.

···

on Mon Apr 11 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:
--
Dave

[plx]

There was a design document linked in one of the earlier discussions that IIRC suggested some collections would want to maintain a "revision count” value, with their indices then holding a snapshot of that “revision count” at their time of creation.

For something like Array that’s a bit heavyweight.

“Invalidation" is also IMHO a bit under-defined without an associated “for what?”:

  var letters = [“a”, “b”, “c”, “d”, “e”]

  // indexOfB == 1
  let indexOfB = letters.indexOf(“b”)

  letters.insert(“z”, atIndex: indexOfB)

…is `index` invalid or not? IMHO it would depend on what you want to do with it.

···

On Apr 13, 2016, at 5:34 AM, Haravikk <swift-evolution@haravikk.me> wrote:

On 13 Apr 2016, at 04:46, plx via swift-evolution <swift-evolution@swift.org> wrote:

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

Oh I agree, that was partly my point though; while this proposal may leave us with the "un-Swifty" issue of being unable to explicitly handle invalidation, it should be possible to solve that later, i.e- this proposal does’t make us any more vulnerable to that problem than we are now, but I definitely agree that we could do with some kind of invalidation mechanism in future that developers can actually implement or respond to. I guess I was more thinking out loud about whether the problem affects the proposal or not, but I don’t think that solving it will place any restrictions on the API as proposed, definitely deserves a proposal of its own once the new indexing system is in place though!

[dabrahams (Dave Abrahams)]

    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
    https://github.com/apple/swift-evolution/blob/master/proposals/0059-updated-set-apis.md

    (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].

In other cases, the mutating pair of methods refer to the receiver, not the
argument.

x = y.union(z) // new value x
y.formUnion(z) // mutates y, not z

x = y.successor(z) // new value x
y.formSuccessor(z) // mutates z (or replaces), not y

This is true, but we need a way to deal with these cases as well.

I think using the form prefix here will confuse this case with the
others, when they are meaningfully different.

I don't think it is confusing, since in these cases the thing being
mutated is always explicitly passed inout (prefixed with &). Obvious,
reasonable people can disagree on this point. IMO, though, if one wants
to avoid “form” here IMO we should have an equally-strong and clear
guideline to replace it for this sort of situation, as it's not
particularly far-fetched to imagine this will come up again.

        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.

It’s an improvement because it is much easier to read and understand what it
means. The phrase “form successor” only makes sense if you dive into the naming
guidelines to see why we have the “form” prefix in the first place.

Or if you see it enough that it becomes natural and you understand what
it means. The same applies to “formUnion,” though. (“InPlace” didn't
have this problem, but... oh, well).

IMO, either “formXXX” is good enough for these kinds of situations, or
it isn't. If it isn't, we should take it out of the guidelines and not
use it for Set. If it is good enough, we should settle on it and let it
proliferate.

Plus, as I said, the form prefix implies a mutation of the wrong
argument.

Not really. “Form” isn't really specific about what's being
mutated. You can form a bowl out of clay or you can form a blockade.
Frankly, I agree with the many people on this list who have said it
carries an implication of non-reflexivity... I just find it to be an
acceptably weak implication; weak enough that we can get away with using
it reflexively.

        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.

Reverse is the best opposite we have of advance, so it makes sense to
me.

Oh, I get it.

Or we could use retreat. =) There are other pairs of words that work
as well, like “increment/decrement”.

Yeah, unfortunately those carry an incorrect implication when the
indices are numbers, because, e.g. the collection might be offsetting
the number by 2 for each position. One could of course argue that using
numbers that way as indices was a bad design choice.

I'll have to think about that idea again. We considered and rejected it
for a reason, but it might not be a really strong one. Thanks for
bringing it up.

It’s rather an implementation detail of the index and collection what
exactly these do,

I think it's fundamental, but I'm not sure that point makes any
difference to our discussion.

but conceptually modeling them as increment and decrement would likely
make intuitive sense to most CS 101 students.

The reason that advance/reverse and increment/decrement work better is because
they are active words that describe what happens to the argument, which has no
other label. “form” describes little about the action that is actually taken on
the argument.

Obviously! The proposed names aren't simply “form.” “Form-” serves
the same purpose as “-ed” or “-ing” in verb-based names. Not a
placeholder, but a modifier used to produce the right semantic
implication.

Therefore, to me it feels like a placeholder or fallback.

That conclusion still doesn't add up for me. However, I do want to give
increment/decrement due consideration.

Thanks again,

···

on Wed Apr 13 2016, Tony Parker <anthony.parker-AT-apple.com> wrote:

    On Apr 12, 2016, at 3:43 PM, Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote:
    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

        - 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

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

--
Dave

[dabrahams (Dave Abrahams)]

        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.

I meant it as a much more exact analogy.

In a collections-move-indices world, you *could* handle indices as pointers have
been handled, bringing in support from the type-system:

enum SaferIndex<T:Comparable> {
case Position(T)
case End
}

…(yes, this is more-or-less `Optional` by another name).

The assumption above is `T` would be today’s “Index” types, w/o the value used
for `endIndex` (e.g. 0..<self.count for an array, the non-`endIndex` values of
`DictionaryIndex` and `SetIndex`, and so on).

No, you can't, at least not usefully. An Index that's at the end of one
collection is in the middle of another, or with a suitably-modified version
of the same collection.

  var x = [1, 2]
  let i = x.index(1, stepsFrom: x.startIndex)
  x.removeLast()
  x[i] // fatal error: Index out of range

The converse is also true: subscripting on a collection's endIndex is
sometimes just fine, even with no mutation in sight.

  let a = (0..<10).reversed()
  print(Array(a)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]”

  let b = a.prefix(9)
  print(Array(b)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1]”

  print(a[b.endIndex]) // “0” (correct, supported behavior)

Of course,

  b[b.endIndex] // As a matter of QOI: fatal error: out of bounds: index >= endIndex

It would’ve been awkward to do this under the previous status quo—e.g. even for
arrays your indices would have to have a back-reference to get the count, and
thus couldn’t be plain integers—but the collection will now always be present to
provide such info.

Cons:

- more overhead than “bare” indices
- doesn’t address invalidation (but what does, really?)

Pros:

- easier in some ways to handle things like e.g 0…Int.max
- the endIndex equivalent *never* invalidates
- compile-time help for end-index checking

Overall this *would* bring the treatment of indices closer to that for `?`—e.g.,
redefine the core type to omit the `nil`-like value,

Sorry, but that's the opposite of what `?` is doing: it *adds* a nil
value.

Seriously, just because Swift has Optionals and they're useful for
safety in some scenarios (compared with allowing everything to be
nullable) does not mean that it's going to be “Swiftier” to apply a
similar pattern everywhere.

use an enum to reintroduce that value when necessary—than to `!`.

I don’t think the above is an *improvement* over the proposal, but it’s a route
that could have been taken.

I believe it would be hard to make such a design work at all, and if you
could make it work I think you'd end up with exactly the problem this
proposal aims to solve: references inside indices. So, I don't think
it's even a possibility, really.

···

on Wed Apr 13 2016, plx <swift-evolution@swift.org> wrote:

    On Apr 12, 2016, at 5:25 PM, Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote:
    on Tue Apr 12 2016, plx > <swift-evolution@swift.org> wrote:

        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.

    --
    Dave

    _______________________________________________
    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

[dabrahams (Dave Abrahams)]

Dmitri, Max, and I just talked this over and we think you're right on
both counts. Having these “index” overloads appear in completion lists
alongside the ones that are there for use as high-level algorithms seems
wrong. Also, since the method either returns a modified version of the
index or modifies the index in place, the index argument is “more
primary” and should come first. Here's what we came up with:

     let j = location(i, offsetBy: 5)

     formLocation(&i, offsetBy: -2)

Feedback welcome.

···

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

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

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

    Thanks for your comments, Brent!

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

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.

--
Dave

[plx]

       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.

I meant it as a much more exact analogy.

In a collections-move-indices world, you *could* handle indices as pointers have
been handled, bringing in support from the type-system:

enum SaferIndex<T:Comparable> {
case Position(T)
case End
}

…(yes, this is more-or-less `Optional` by another name).

The assumption above is `T` would be today’s “Index” types, w/o the value used
for `endIndex` (e.g. 0..<self.count for an array, the non-`endIndex` values of
`DictionaryIndex` and `SetIndex`, and so on).

No, you can't, at least not usefully. An Index that's at the end of one
collection is in the middle of another, or with a suitably-modified version
of the same collection.

Sure, in certain concrete scenarios it’s possible for one collection’s indices to have such relationships to some other collection.

But, what of it?

In a generic context you can’t assume this; in a concrete context you naturally have more information.

Slices would become problematic, I’ll grant.

var x = [1, 2]
let i = x.index(1, stepsFrom: x.startIndex)
x.removeLast()
x[i] // fatal error: Index out of range

Indices can become invalid; this imposes preconditions. I don’t get it.

The converse is also true: subscripting on a collection's endIndex is
sometimes just fine, even with no mutation in sight.

let a = (0..<10).reversed()
print(Array(a)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]”

let b = a.prefix(9)
print(Array(b)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1]”

print(a[b.endIndex]) // “0” (correct, supported behavior)

I believe we are back to “subscripting one collection with *another* collection's `endIndex`, no?

Are there any circumstances where a collection *can* be usefully-subscripted with its *own* `endIndex`?

Of course,

b[b.endIndex] // As a matter of QOI: fatal error: out of bounds: index >= endIndex

It would’ve been awkward to do this under the previous status quo—e.g. even for
arrays your indices would have to have a back-reference to get the count, and
thus couldn’t be plain integers—but the collection will now always be present to
provide such info.

Cons:

- more overhead than “bare” indices
- doesn’t address invalidation (but what does, really?)

Pros:

- easier in some ways to handle things like e.g 0…Int.max
- the endIndex equivalent *never* invalidates
- compile-time help for end-index checking

Overall this *would* bring the treatment of indices closer to that for `?`—e.g.,
redefine the core type to omit the `nil`-like value,

Sorry, but that's the opposite of what `?` is doing: it *adds* a nil
value.

…I must have been unclear.

Step 1: Define T* = { "all memory addresses” (nil included) }
Step 2: Define T = T* \ { nil } (e.g. "non-null pointers")

…is what I was trying to summarize via “redefine the core type to omit the `nil`-like value” (which is the important part here).

Anyways, having `endIndex` directly inhabit the same type as the “good” indices has some pros and some cons; it’s not an IMHO one-sided situation as with `nil`.

On the one hand, in my own experience so far, it’s definitely been the case that most custom collections I’d done have had indices that’re effectively the `SaferIndex` above; it’s been rather rare that there’s been a natural “1 past the rest” value to use of the same type as is used to describe the position of a “good” index.

Seriously, just because Swift has Optionals and they're useful for
safety in some scenarios (compared with allowing everything to be
nullable) does not mean that it's going to be “Swiftier” to apply a
similar pattern everywhere.

use an enum to reintroduce that value when necessary—than to `!`.

I don’t think the above is an *improvement* over the proposal, but it’s a route
that could have been taken.

I believe it would be hard to make such a design work at all, and if you
could make it work I think you'd end up with exactly the problem this
proposal aims to solve: references inside indices. So, I don't think
it's even a possibility, really.

I can’t say I see the impossibility. I definitely have experienced the clunkiness.

This is getting too involved for a hypothetical I was explaining, but not advocating.

This proposal and the new design is a good design!

···

On Apr 13, 2016, at 5:36 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Wed Apr 13 2016, plx <swift-evolution@swift.org> wrote:

   On Apr 12, 2016, at 5:25 PM, Dave Abrahams via swift-evolution >> <swift-evolution@swift.org> wrote:
   on Tue Apr 12 2016, plx >> <swift-evolution@swift.org> wrote:

       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.

   --
   Dave

   _______________________________________________
   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

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

[plx]

Seriously, just because Swift has Optionals and they're useful for
safety in some scenarios (compared with allowing everything to be
nullable) does not mean that it's going to be “Swiftier” to apply a
similar pattern everywhere.

This reminds me of something I was going to ask about earlier and forgot.

Coming from other languages, I’ve definitely brought with me an assumption that “make invalid states unrepresentable (except where unavoidable)” is the right way to go, with deviations from that rule requiring scrutiny.

Is that outlook actually something the core team considers “Swift-y” or not, though?

The connection to the point you’re making here and the question is that adopting this design style *will* lead to lots of optionals in lots of places.

···

On Apr 13, 2016, at 5:36 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Wed Apr 13 2016, plx <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

use an enum to reintroduce that value when necessary—than to `!`.

I don’t think the above is an *improvement* over the proposal, but it’s a route
that could have been taken.

I believe it would be hard to make such a design work at all, and if you
could make it work I think you'd end up with exactly the problem this
proposal aims to solve: references inside indices. So, I don't think
it's even a possibility, really.

       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.

   --
   Dave

   _______________________________________________
   swift-evolution mailing list
   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

--
Dave

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

[trs (Thorsten Seitz)]

+1 to Tony's arguments and to increment/decrement

-Thorsten

···

Am 13.04.2016 um 17:45 schrieb Tony Parker via swift-evolution <swift-evolution@swift.org>:

On Apr 12, 2016, at 3:43 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

Thanks for your review, Tony!

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:

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
https://github.com/apple/swift-evolution/blob/master/proposals/0059-updated-set-apis.md
(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].

In other cases, the mutating pair of methods refer to the receiver, not the argument.

x = y.union(z) // new value x
y.formUnion(z) // mutates y, not z

x = y.successor(z) // new value x
y.formSuccessor(z) // mutates z (or replaces), not y

I think using the form prefix here will confuse this case with the others, when they are meaningfully different.

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.

It’s an improvement because it is much easier to read and understand what it means. The phrase “form successor” only makes sense if you dive into the naming guidelines to see why we have the “form” prefix in the first place. Plus, as I said, the form prefix implies a mutation of the wrong argument.

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.

Reverse is the best opposite we have of advance, so it makes sense to me. Or we could use retreat. =) There are other pairs of words that work as well, like “increment/decrement”. It’s rather an implementation detail of the index and collection what exactly these do, but conceptually modeling them as increment and decrement would likely make intuitive sense to most CS 101 students.

The reason that advance/reverse and increment/decrement work better is because they are active words that describe what happens to the argument, which has no other label. “form” describes little about the action that is actually taken on the argument. Therefore, to me it feels like a placeholder or fallback.

- Tony

- 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

_______________________________________________
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

[dabrahams (Dave Abrahams)]

Quick thought:

Why are you reaching for the "form..." rule for the mutating methods when there
are clear verb counterparts?
location: locate
successor: succeed

We're not using successor(i) anymore, as noted below, and furthermore
c.succeed(&i) strongly implies the wrong meaning. I didn't consider
using

  c. locate(...:&i ... )

primarily because I never thought of it and nobody suggested it IIRC,
but I also don't see how it would work in a family with
c.location(after: i) et al. Suggestions?

···

on Mon Apr 25 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

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

    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.

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

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

    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
   >
    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
   >.

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

    --
    Dave

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

--
Dave

[xwu (Xiaodi Wu)]

> Quick thought:
>
> Why are you reaching for the "form..." rule for the mutating methods
when there
> are clear verb counterparts?
> location: locate
> successor: succeed

We're not using successor(i) anymore, as noted below, and furthermore
c.succeed(&i) strongly implies the wrong meaning.

I thought that's what I understood from the email, but in the linked
proposal they're still there (as are the many types of Range protocols).
Wrong link, or just not updated?

I didn't consider
using

  c. locate(...:&i ... )

primarily because I never thought of it and nobody suggested it IIRC,
but I also don't see how it would work in a family with
c.location(after: i) et al. Suggestions?

I didn't read this proposal carefully on its initial presentation for
review. Looking at it now, I wonder about the wisdom of "location"--I
understand the rationale of avoiding multiple methods named "index" that do
different things, but these particular functions return or mutate indices,
and nowhere else are these called "locations". If you're asking for
possible alternative suggestions to avoid using "index", I'll suggest the
following here because I don't recall seeing them offered previously. They
read as phrases or sentences:

// taking inspiration from ForwardIndexType, which is no more...
c.advancing(_ i: Index, by offset: IndexDistance, limit: Index)
c.advance(_ i: inout Index, by offset: IndexDistance, limit: Index)

// or alternatively, using the terminology in the comments that sit above
`location`
c.offsetting(_ i: Index, by n: IndexDistance, limit: Index)
c.offset(_ i: inout Index, by n: IndexDistance, limit: Index)

// and then, in place of successor, etc.
c.incrementing(_ i: Index, limit: Index)
c.increment(_ i: inout Index, limit: Index)
c.decrementing(_ i: Index, limit: Index)
c.decrement(_ i: inout Index, limit: Index)

("'Limit' doesn't read like a phrase," you might say. Well, think of a
coupon: "$1 off one tub of margarine. Limit one per purchase. Void if
transferred or sold.")

···

On Mon, Apr 25, 2016 at 6:15 PM, Dave Abrahams <dabrahams@apple.com> wrote:

on Mon Apr 25 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

> On Mon, Apr 25, 2016 at 1:24 PM, Dave Abrahams via swift-evolution > > <swift-evolution@swift.org> wrote:
>
> 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.
>
> The final revisions are reflected in the latest version of the
> proposal:
>
>
https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
>
> 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
> >
> 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
> >.
>
> P.S. If anyone is interested in contributing, there are still plenty
of
> FIXMEs left for us to handle ;-)
>
> --
> Dave
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

--
Dave

[Brent_Royal-Gordon]

(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.)

Hi Brent,

Could you explain what kind of safety do you have in mind? Swift will
guarantee memory safety even if you attempt to advance an index past
endIndex using the non-limiting overload.

By "safety" here, I mean what I will call "index safety": not accidentally using an index which would violate the preconditions of the methods or properties you are planning to use it with. I think it's too easy to accidentally overrun the permitted range of indices, and the API should help you avoid doing that.

For instance, suppose I'm porting XCTest to Swift, and I decide to rewrite its `demangleSimpleClass` function, which extracts the identifiers from a mangled Swift symbol name. Specifically, I'm implementing `scanIdentifier`, which reads one particular identifier out of the middle of a string. (For those unfamiliar: an identifier in a mangled symbol name consists of one or more digits to represent a length, followed by that many characters.) I will assume that the mangled symbol name is in a Swift.String.

Here's a direct port:

  func scanIdentifier(partialMangled: String) -> (identifier: String, remainder: String) {
    let chars = partialMangled.characters
    var lengthRange = chars.startIndex ..< chars.startIndex
  
    while chars[lengthRange.endIndex].isDigit {
      lengthRange.endIndex = chars.successor(of: lengthRange.endDigit)
    }
  
    let lengthString = String(chars[lengthRange])
    let length = Int(lengthString)!
  
    let identifierRange = lengthRange.endIndex ..< chars.index(length, stepsFrom: lengthRange.endIndex)
    let remainderRange = chars.suffix(from: identifierRange.endIndex)
  
    return (String(chars[identifierRange]), String(chars[identifierRange]))
  }

This works (note: probably, I haven't actually tested it), but it fails a precondition if the mangled symbol is invalid. Suppose we want to detect this condition so that our parent function can throw a nice error instead:

  func scanIdentifier(partialMangled: String) -> (identifier: String, remainder: String)? {
    let chars = partialMangled.characters
    var lengthRange = chars.startIndex ..< chars.startIndex
  
    while chars[lengthRange.endIndex].isDigit {
      lengthRange.endIndex = chars.successor(of: lengthRange.endDigit)
      if lengthRange.endIndex == chars.endIndex {
        return nil
      }
    }
  
    let lengthString = String(chars[lengthRange])
    guard let length = Int(lengthString) else {
      return nil
    }
  
    let identifierRange = lengthRange.endIndex ..< chars.index(length, stepsFrom: lengthRange.endIndex)
    if identifierRange.endIndex > chars.endIndex {
      return nil
    }
  
    let remainderRange = chars.suffix(from: identifierRange.endIndex)
  
    return (String(chars[identifierRange]), String(chars[identifierRange]))
  }

That's really not the greatest. To tell the truth, I've actually guessed what bounds-checking is needed here; I'm not 100% sure I caught all the cases. And, um, I'm not really sure that `index(length, stepsFrom: lengthRange.endIndex)` is guaranteed to return anything valid if `length` is too large. Even `limitedBy:` wouldn't help me here—I would end up silently accepting and truncating an invalid string instead of detecting the error.

Now, imagine if `successor(of:)` and `index(_:stepsFrom:)` instead had variants which performed range checks on their results and returned `nil` if they failed:

  func scanIdentifier(partialMangled: String) -> (identifier: String, remainder: String)? {
    let chars = partialMangled.characters
    var lengthRange = chars.startIndex ..< chars.startIndex
  
    while chars[lengthRange.endIndex].isDigit {
      guard let nextIndex = chars.successor(of: lengthRange.endDigit, permittingEnd: false) else {
        return nil
      }
      lengthRange.endIndex = nextIndex
    }
  
    let lengthString = String(chars[lengthRange])
    guard let length = Int(lengthString) else {
      return nil
    }
  
    guard let identifierEndIndex = chars.index(length, stepsFrom: lengthRange.endIndex, permittingEnd: true) else {
      return nil
    }
  
    let identifierRange = lengthRange.endIndex ..< identifierEndIndex
    let remainderRange = chars.suffix(from: identifierRange.endIndex)
  
    return (String(chars[identifierRange]), String(chars[identifierRange]))
  }

By using these variants of the index-manipulation operations, the Collection API itself tells me where I need to handle bounds-check violations. Just like the failable `Int(_: String)` initializer, if I forget to check bounds after manipulating an index, the code will not type-check. That's a nice victory for correct semantics.

* * *

Incidentally, rather than having Valid<Index>, an alternative would be to have Unchecked<Index>. This would mark an index which had *not* been checked. You could use its `uncheckedIndex` property to access the index directly, or you could pass it to `Collection.check(_: Unchecked<Index>) -> Index?` to perform the check.

This would not serve to eliminate redundant checks; it would merely get the type system to help you catch index-checking mistakes. You could, of course, perform the check and then invalidate the index with a mutation, but that's just as true today. I believe that, with aggressive enough optimization, this could be costless at runtime. *And* it would offer a way to provide the so-called "safe indexing" many people ask for: you could offer a subscript which took an Unchecked<Index> and returned an Optional<Element>.

···

--
Brent Royal-Gordon
Architechies