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

trs · April 16, 2016, 11:12am

Path dependent types as used in Scala would allow making this distinction type safe (see http://docs.scala-lang.org/tutorials/tour/inner-classes or http://danielwestheide.com/blog/2013/02/13/the-neophytes-guide-to-scala-part-13-path-dependent-types.html\) by allowing the index type to be rooted at the instance.

Are there any plans to adding path dependent types to Swift?

-Thorsten

···

Am 15.04.2016 um 23:19 schrieb Dmitri Gribenko via swift-evolution <swift-evolution@swift.org>:

On Fri, Apr 15, 2016 at 1:30 PM, Stephan Tolksdorf <st@quanttec.com> wrote:

On 2016-04-12 Dmitri Gribenko via swift-evolution wrote:

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.

The proposal requires Index values to be Comparable. Does that mean that
indices from different collection instances should be comparable i.e. have a
strict total order?

No, comparing indices from unrelated instances produces unspecified
results (incl. traps).

trs · April 18, 2016, 6:34am

The nonmutating forms successor/predecessor were fine. No need to match them with the mutating ones IMO.

-Thorsten

···

Am 13.04.2016 um 21:57 schrieb Dave Abrahams via swift-evolution <swift-evolution@swift.org>:

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

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.

...and having talked it over at lunch, now I remember why we rejected
it: there's no good way to make a nonmutating version.

let x = c.incremented(i) // reads like an assertion about the past
let y = c.incrementing(i) // reads like it has side-effects and returns c, or
// a new version of c

APIs where the receiver returns a modified version of an argument don't
lend themselves to verb forms.

--
Dave

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

Patrick_Smith · April 26, 2016, 7:49am

Yes, I too find the naming confusing. I think the method should contain
'index', either in the prefix or as a parameter label, so if you searched
through Collection’s methods you’d be able to find every one that was to do
with indexes.

Sorry to suggest more ideas, but here is a theoretical API with index in the
prefix: (the noun is ‘index’)

func index(_ index: Index, offsetBy n: IndexDistance) -> Index

func index(_ index: Index, offsetBy n: IndexDistance, limitedBy limit: Index)
-> Index

func formIndex(_ index: inout Index, offsetBy n: IndexDistance)

func formIndex(_ index: inout Index, offsetBy n: IndexDistance, limitedBy
limit: Index)

And here is one within a parameter: (the verb is ‘offset’)

func offsetted(index: Index, by n: IndexDistance) -> Index

func offsetted(index: Index, by n: IndexDistance, limitedBy limit: Index)
-> Index

func offset(index: inout Index, offsetBy n: IndexDistance)

func offset(index: inout Index, offsetBy n: IndexDistance, limitedBy limit:
Index)

**Patrick Smith**

> On Mon, Apr 25, 2016 at 6:15 PM, Dave Abrahams
<[dabrahams@apple.com](mailto:dabrahams@apple.com)> wrote:
>
> on Mon Apr 25 2016, Xiaodi Wu <[xiaodi.wu-AT-
gmail.com](http://xiaodi.wu-AT-gmail.com)> wrote:
>
> > 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?

My mistake; I pushed to the wrong repo. Please try again.

I see a new version, but I still see .successor().

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

As I've said before, the “ing” suffix strongly implies we're returning
(a version of) `c`, not of `i`. c.f.

   Please hand me **your coat, emptying the left pocket**.

You're not going to get a pocket; you're getting a whole coat.

Quite right; didn't mean to retread that. I feel the same deficiency applies

to using the "form" convention, though, in that (at least as has been
discussed on this list) the convention usually refers to the receiver being
mutated. Thus, `c.formLocation(...)` sounds like `c` should be mutated in some
way.

One way out that I can think of is looking to good ol' Objective-C

conventions. By this I mean that, in my mind, shorter method names like
`str.appending(...)` are derived by omitting redundant words from longer
ancestral names such as `str.stringByAppendingString(...)`. In this particular
case, certain words are not redundant and perhaps we should just bravely put
back those words that are necessary to clarify.

That is, if this were Objective-C, we'd have something like

"indexByAdvancingIndex". You're quite right that we can't use just "advancing"
because it implies returning a version of the receiver. We've tried "index",
but then it conflicts with another method "index". Now there's renaming
"index" to "location", even though it returns a thing of type Index... Aren't
the most succinct but still accurate method names instead:
`c.indexByAdvancing(i, ...)` and `c.advanceIndex(&i, ...)`? [Incidentally,
`c.advance` might read like c is being advanced.]

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

the limit label is the least of my concerns here :-)

That said, orthogonally, I feel like many `limitedBy` labels can be

simplified to `limit` :)

> > On Mon, Apr 25, 2016 at 1:24 PM, Dave Abrahams via swift-
evolution
> > <[swift-evolution@swift.org](mailto:swift-
evolution@swift.org)> wrote:
> >
> > on Wed Apr 20 2016, Chris Lattner <[swift-
evolution@swift.org](mailto:swift-evolution@swift.org)> wrote:
> >
> > > On Apr 10, 2016, at 2:41 PM, Chris Lattner
> > > <[clattner@apple.com](mailto: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%2
d448E%2d8C70%2d6E7400629BC0%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](mailto:swift-evolution@swift.org)
> > <https://lists.swift.org/mailman/listinfo/swift-evolution>
> >
>
> \--
> Dave
>

\--

Dave

···

On Apr 26 2016, at 11:52 am, Xiaodi Wu via swift-evolution <swift- evolution@swift.org> wrote:

On Mon, Apr 25, 2016 at 8:25 PM, Dave Abrahams <[dabrahams@apple.com](mailto:dabrahams@apple.com)> wrote:

on Mon Apr 25 2016, Xiaodi Wu <[xiaodi.wu-AT-gmail.com](http://xiaodi.wu- AT-gmail.com)> wrote:

Brent_Royal-Gordon · April 13, 2016, 5:12am

I want to make a point that avoiding precondition violations by
removing preconditions is not the solution. When you design an API,
it frequently has some constraints on the arguments or on the
execution environment, which, when violated, prevent the API from
performing the operation correctly.

I totally agree with this section, and I've made similar arguments in the past on this list. For instance, I've been critical in the past of suggestions that failable initializers should be removed, or that all subscripts should be Optional.

Let's talk about how this applies to Collection.

For example, Collection APIs in question that work with indices are
primitive APIs that the rest of Collection APIs build upon. One of
these APIs, basically the reason why indices exist, is
Collection.subscript(Index). Today the behavior is unspecified if the
index is not valid. If we follow the principle that you outlined:

not accidentally using an index which would violate the preconditions of the methods or properties you are planning to use it with.

Collection.subscript(Index) should return an optional. Does this
match your expectations? If so, how do you imagine even trivial
algorithms written?

for i in data.indices {
data[i]! = data[i]! * 2 // assume that 'data[i]!' can be made settable.
}

Yes, I totally agree that `Collection.subscript(_: Index)` should not be Optional.

But I think that index-manipulation methods like `successor(of:)` are a different story. It is normal and expected that, when you alter an index, you will occasionally hit the boundaries of the collection. There certainly are cases where you know a particular index manipulation is safe, but most index manipulations need to be guarded by something like:

  while index < collection.endIndex {
    let nextIndex = collection.successor(of: index)
    …
    index = nextIndex
  }

In these cases, it would be better if the `successor(of:)` method was designed in a way that acknowledged and encapsulated the bounds check that is usually required when it is used:

  while let nextIndex = collection.successor(of: index) {
    …
    index = nextIndex
  }

Given the difficulties of statically detecting index invalidation, I totally agree that (as you discussed in a section I've snipped) we can't statically prove indexes are safe. But we can, at the point where we generate an index, easily check if that index is *currently* valid. And it's something that most callers will have to do anyway if we don't do it ourselves.

However…

I would like to draw attention to the following part:

// Approach #3: change Collection.index(_:stepsFrom:limitedBy:) to return an
// optional index.
//
// This method has to perform the range check to stop advancing the index when
// it reaches the limit. Currently it just discards the information about
// whether it reached the limit or not. Instead, it can cheaply return it to
// the caller.
//
// Note that the same logic does not apply to other
// Collection.index(_:stepsFrom:) overloads.

We will change the index(_:stepsFrom:limitedBy:) overload to return an
optional, and we will see what other implications it has, and how it
fits into the rest of the system.

I'm glad to hear you'll evaluate this option, and I think it can give us both what we want from this API.

I think having the most high-level operations incorporate bounds checks, while the lower-level ones don't, is a good compromise. If we encourage people to use `index(_:stepsFrom:limitedBy:)` unless they know what they're doing, naïve clients will get an implicit bounds check, while sophisticated, speed-sensitive clients can use methods like `successor(of:)` which require them to check bounds manually.

(There might even be a case for offering bounds-checked `successor(of:limitedBy:)` and `predecessor(of:limitedBy:)` methods to give people bounds-checked alternatives to all three.)

Thanks again, Brent.

Thank you!

···

--
Brent Royal-Gordon
Architechies

dabrahams · April 13, 2016, 10:41pm

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.

...and having talked it over at lunch, now I remember why we rejected
it: there's no good way to make a nonmutating version.

let x = c.incremented(i) // reads like an assertion about the past
let y = c.incrementing(i) // reads like it has side-effects and returns c, or
// a new version of c

In fact, it does return a new version* of c; just like this:

let s2 = myString.appending(“foo”)

*new version: the result is related to the argument

Uhh, that is *really* stretching the concept of “new version.” By that
logic, every method that returns non-void is returning a new version of
the receiver.

This works out great:

let next = c.incrementing(first)
c.increment(&next)

It only works great if we give up the idea that there's supposed to be
some correspondence between how adding “ing” affects meaning in English
and how it affects meaning in our APIs. If I say to you, “give me your
coat, emptying the pockets,” I expect to get a modified version of your
coat, not of what's in the pocket.

···

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

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

--
Dave

dabrahams · April 14, 2016, 4:53pm

Interesting idea. Predecessor and successor are more specific, because
the predecessor of the predecessor of i is still “before” i, but that
may not be a strong enough reason.

···

on Wed Apr 13 2016, Shawn Erickson <shawnce-AT-gmail.com> wrote:

On Wed, Apr 13, 2016 at 4:45 PM Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote:

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

I like the use of `location(...)` instead of `index(...)`. I strongly suggest
that successor and predecessor become `location(after:)` and `location(before:)
` (or something like that) so that the index manipulation API are all similarly
named.

--
Dave

hlovatt · April 16, 2016, 10:17pm

+1 for Scala's path dependent types.

···

On Saturday, 16 April 2016, Thorsten Seitz via swift-evolution < swift-evolution@swift.org> wrote:

> Am 15.04.2016 um 23:19 schrieb Dmitri Gribenko via swift-evolution <
swift-evolution@swift.org <javascript:;>>:
>
> On Fri, Apr 15, 2016 at 1:30 PM, Stephan Tolksdorf <st@quanttec.com > <javascript:;>> wrote:
>> On 2016-04-12 Dmitri Gribenko via swift-evolution wrote:
>>>
>>> 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.
>>
>>
>> The proposal requires Index values to be Comparable. Does that mean that
>> indices from different collection instances should be comparable i.e.
have a
>> strict total order?
>
> No, comparing indices from unrelated instances produces unspecified
> results (incl. traps).

Path dependent types as used in Scala would allow making this distinction
type safe (see http://docs.scala-lang.org/tutorials/tour/inner-classes or
http://danielwestheide.com/blog/2013/02/13/the-neophytes-guide-to-scala-part-13-path-dependent-types.html\)
by allowing the index type to be rooted at the instance.

Are there any plans to adding path dependent types to Swift?

-Thorsten

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

--
-- Howard.

trs · April 18, 2016, 6:14am

Preventing indices of one collection being used by another collection can be done by using path dependent types like in Scala.

Then 'i' would have type a.Index (where 'a' is the instance!) and therefore b[i] would not typecheck as it would require an index of type b.Index

-Thorsten

···

Am 13.04.2016 um 03:39 schrieb Dmitri Gribenko via swift-evolution <swift-evolution@swift.org>:

Ok, mutation can invalidate indices. Can immutability help?

---
let a = [1, 2, 3]
let b: [Int] =
let i = a.check(a.startIndex)
b[i] // trap
---

Since it is not possible to encode the validity relationship in the
type system, we want to encourage these operations to trap if they
detect violations.

dabrahams · April 18, 2016, 9:52pm

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;

That's incorrect. A slice's indices are *documented* as having a
particular relationship to those of the thing it was sliced from. This
applies everywhere. A dictionary's keys and values use the same indices
as the dictionary itself, and have a correspondence.

You’re right, of course; I rarely use slices and completely overlooked
them.

I also phrased it badly, b/c what I was trying to express is that code
like the below is (I think?) unlikely to work generically:

  extension Collection where Element:Equatable {

     // plz don’t do this
     func hasValueMismatch(with other: Self, at index: Index) -> Bool {
       return self[index] != other[index]
     }

     // plz don’t do this either
    func hasValueMismatch<K:Collection where K.Index == Index, K.Element == Self.Element>(with other: K, at index: Index) -> Bool {
      return self[index] != other[index]
    }

  }

…(you would’t write the above anyway, but it illustrates the kind of
"generic context" I had in mind when I wrote it).

Yes, I understand that you weren't thinking of the cases where indices
from different collections *do* have a relationship in a generic context
:-).

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.

My point is that whether i is at the end or not cannot be encoded in i.

I see the miscommunication, now. Of course you can’t encode that.

How can this be a miscommunication? Your examples from earlier in the
thread include this:

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

which clearly does try to encode that information in the index.

I’ve put a couple examples down below as a last effort at
communicating what I’m getting at 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?

Totally legit, as mentioned above. a.prefix(9) returns a slice of a.

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

var a = [1]
let i = a.endIndex
a.append(2)
print(a[i]) // “2”

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

Sorry, that's still unclear to me. I just don't see what you're getting
at.

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

Maybe, but my point is that many things in the current model are
incompatible with the other arrangement. If you wanted to change the
arrangement, you'd need to re-think the current model from the ground
up, including index invalidation, how algorithms interact, the
relationship of slices to the thing they're sliced from, etc...

So what you're suggesting is an interesting hypothesis, but to me it's
not by any means obviously workable.

You’re completely right about slices. I’ll provide a couple concrete examples before addressing the rest.

Here are three collection-combinators (or adapters I think you’d call them):

  // Collection with elements of A, then elements of B.
  struct ChainCollection<A:Collection,B:Collection> : Collection {
    let a: A; let b: B;
  }

  // Collection with elements `(a,b)` for each pair in the cartesian product of `A` and `B`.
  struct ProductCollection<A:Collection,B:Collection> : Collection {
    let a: A; let b: B;
  }

  // Collection with adjacent elements from A
  struct AdjacentElementCollection<A:Collection> : Collection {
    let a: A
  }

…each of which I’ve declared `: Collection` but each which will still need some suitable `Index` implementation.

Here’s one way to write these indices (henceforth, the V1 indices):

  // `endIndex` will be .InB(b.endIndex)
  enum ChainCollectionIndex<A:Collection,B:Collection> {
    // Precondition: the index isn’t `a.endIndex`.
    case InA(A.Index)
    case InB(B.Index)
  }

  // `endIndex` will have both `.aIndex` and `.bIndex` equal to their “source”'s `endIndex`
  struct ProductCollectionIndex<A:Collection,B:Collection> {
    let aIndex: A.Index
    let bIndex: B.Index
  }

  // `endIndex` will be both of these set to `a.endIndex`
  // - all other situations expect `upper` is `lower`’s successor, and both != `endIndex`
  struct AdjacentElementCollectionIndex<A:Collection> {
    let lower: A.Index
    let upper: A.Index
  }

…(I trust the index-manipulation boilerplate is easy to fill-in).

There’s absolutely nothing wrong with the above! Each of these types
has the capability to represent the “good” indices, and also has a
reasonable way to represent `endIndex` values.

But, they could also be written like so (henceforth, the V2 indices):

  enum ChainCollectionIndex<A:Collection,B:Collection> {
    // Precondition: the index isn’t `a.endIndex`.
    case InA(A.Index)
    // Precondition: the index isn’t `b.endIndex`.
    case InB(B.Index)
    // `endIndex` sentinel
    case End
  }

  enum ProductCollectionIndex<A:Collection,B:Collection> {
    // Precondition: neither index is the source collection’s `endIndex`
    case Item(A.Index, B.Index)
    // `endIndex` sentinel
    case End
  }

  enum AdjacentElementCollectionIndex<A:Collection> {
    // Precondition: `upper` is `lower`’s successor, *both* are != `a.endIndex`
    case Adjacency(lower: A.Index, upper: A.Index)
    // `endIndex` sentinel
    case End
  }

…each of which is essentially the V1 version, except now with a
dedicated `endIndex` value tacked-on.

Again you're encoding “I'm at the end” in the index, which as we've
agreed does not work.

Tacking on the dedicated `endIndex` isn’t necessary, but at least for
me taking V2-style approaches has been very advantageous.

Most of the advantage has been from being able to enforce stricter
invariants on the non-endIndex indices,

I don't see how anything is lost in terms of the ability to enforce
invariants, if the collection handles index movement.

which generally makes the code simpler and also easier to reason
about; I’m also fortunate in that I’m not working on the standard
library, and thus can choose how heavily to weight “time to correct
implementation” vis-a-vis “proximity to maximum possible efficiency”.

The above indices are drawn from what are admittedly simple
combinators/adaptors, but they feel like representative examples for
me; even for fancier, actually-custom things it’s almost always been
much more natural to go with a V2-style index (and sometimes no
natural V1-style approach even exists).

I’ve done a fair amount of experimenting with the model implied
above—moving `endIndex` into a dedicated sentinel, etc.—and although
it’s pretty easy overall to translate back and forth between the two
models, the “alternative” approach *at best* comes out a wash...at
best.

For the most part, invalidation is about the same between the two
models for all non-end-index—for such indices, the same mutations
invalidate the same indices under either approach.

What *is* different between the two is that a cached `endIndex` will never become valid due to mutation, e.g. this won’t happen:

  // status quo:
  var items = [“a”, “b”]
  let cachedEndIndex = items.endIndex // this is just `2`
  items.append[“c”]
  items[cachedEndIndex] // returns “c"

  // dedicated `endIndex`:
  var items = [“a”, “b”]
  let cachedEndIndex = items.endIndex
  items.append[“c”]
  items[cachedEndIndex] // goes boom, b/c `cachedEndIndex` is still the `endIndex`

So one special index value “moves automatically as the collection changes” and
all others do not. Doesn't seem like an advantage to me. It's easy to
imagine having subtle bugs due to this difference.

…and things like this wouldn't work the same way:

  // status quo:
  var items = [“a”, “b”]
  let cachedEndIndex = items.endIndex // this is just `2`
  items.insert(“c”, at: cachedEndIndex) // [“a”, “b”, “c”]
  items.insert(“d”, at: cachedEndIndex) // [“a”, “b”, “d”, “c”]

  // dedicated `endIndex`
  var items = [“a”, “b”]
  let cachedEndIndex = items.endIndex // this is `.End`
  items.insert(“c”, at: cachedEndIndex) // [“a”, “b”, “c”]
  items.insert(“d”, at: cachedEndIndex) // [“a”, “b”, “c", “d”]

…because the end-index sentinel would *always* refer to the logical
end of the collection.

Yeah, that difference seems like an active problem to me.

Slices would truly be problematic here. For the rest, it’s hard to see
insurmountable difficulties—especially given the ease of converting
between the two approaches, given access to the collection—but I’d
expect it to be far clunkier and a tad slower.

Not sure what you're saying would be clunkier. I can tell you that
having a special-case index state for “past the end” is a great way to
introduce both clunky special-case code to manage the differences in
representation and behavior, and associated inefficiency.

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.

I will happily agree to drop this topic :-)

It’s dropped, now; I only felt the need to reply one more time b/c I
could tell I’d previously failed to communicate clearly-enough.

Agh. I had forgotten my offer to drop this and now I've written this
whole reply, which might have some value so sending. But I promise I
won't answer again!

···

on Thu Apr 14 2016, plx <swift-evolution@swift.org> wrote:

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

This proposal and the new design is a good design!

Thanks!

I really do mean it! Just look at those examples and think of how many
redundant back-references they used to need...

      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

_______________________________________________
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

--
Dave

dabrahams · April 18, 2016, 9:54pm

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.

The proposal requires Index values to be Comparable. Does that mean that
indices from different collection instances should be comparable i.e. have a
strict total order?

No, comparing indices from unrelated instances produces unspecified
results (incl. traps).

Path dependent types as used in Scala would allow making this
distinction type safe (see
http://docs.scala-lang.org/tutorials/tour/inner-classes or
http://danielwestheide.com/blog/2013/02/13/the-neophytes-guide-to-scala-part-13-path-dependent-types.html\)
by allowing the index type to be rooted at the instance.

Wouldn't that also rule out useful designs, as in those where indices
into one collection are stored in another?

Are there any plans to adding path dependent types to Swift?

I don't know of any, but that doesn't really mean much.

···

on Sat Apr 16 2016, Thorsten Seitz <swift-evolution@swift.org> wrote:

Am 15.04.2016 um 23:19 schrieb Dmitri Gribenko via swift-evolution <swift-evolution@swift.org>:
On Fri, Apr 15, 2016 at 1:30 PM, Stephan Tolksdorf <st@quanttec.com> wrote:

On 2016-04-12 Dmitri Gribenko via swift-evolution wrote:

--
Dave

dabrahams · April 18, 2016, 9:57pm

The nonmutating forms successor/predecessor were fine. No need to
match them with the mutating ones IMO.

Our API guidelines say that we should match them. We should have a
better reason to depart from the API guidelines than “some people don't
like the results in this case.” And if the guidelines are inadequate
for handling cases like this, we should fix them.

···

on Sun Apr 17 2016, Thorsten Seitz <swift-evolution@swift.org> wrote:

-Thorsten

Am 13.04.2016 um 21:57 schrieb Dave Abrahams via swift-evolution <swift-evolution@swift.org>:

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

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.

...and having talked it over at lunch, now I remember why we rejected
it: there's no good way to make a nonmutating version.

let x = c.incremented(i) // reads like an assertion about the past
let y = c.incrementing(i) // reads like it has side-effects and returns c, or
// a new version of c

APIs where the receiver returns a modified version of an argument don't
lend themselves to verb forms.

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

Haravikk3 · April 26, 2016, 8:52am

I prefer the index() method name for this purpose, but I wonder if we might want to consider overloads for forward/backward, since not all indexes are bidirectional (or at least, not efficiently so), for example:

index(_ index:Index, advancedBy:Index.Distance) -> Index
index(_ index:Index, reversedBy:Index.Distance) -> Index // Only declared where Self.Index : BidirectionalIndexType?

But yeah, everything related to index manipulation should be doable from some variant of .index() I think.

···

On 26 Apr 2016, at 08:49, Patrick Smith via swift-evolution <swift-evolution@swift.org> wrote:

Yes, I too find the naming confusing. I think the method should contain 'index', either in the prefix or as a parameter label, so if you searched through Collection’s methods you’d be able to find every one that was to do with indexes.

Sorry to suggest more ideas, but here is a theoretical API with index in the prefix: (the noun is ‘index’)

func index(_ index: Index, offsetBy n: IndexDistance) -> Index
func index(_ index: Index, offsetBy n: IndexDistance, limitedBy limit: Index) -> Index

func formIndex(_ index: inout Index, offsetBy n: IndexDistance)
func formIndex(_ index: inout Index, offsetBy n: IndexDistance, limitedBy limit: Index)

And here is one within a parameter: (the verb is ‘offset’)

func offsetted(index: Index, by n: IndexDistance) -> Index
func offsetted(index: Index, by n: IndexDistance, limitedBy limit: Index) -> Index

func offset(index: inout Index, offsetBy n: IndexDistance)
func offset(index: inout Index, offsetBy n: IndexDistance, limitedBy limit: Index)

Patrick Smith
On Apr 26 2016, at 11:52 am, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:
On Mon, Apr 25, 2016 at 8:25 PM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

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

> On Mon, Apr 25, 2016 at 6:15 PM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:
>
> on Mon Apr 25 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com <http://xiaodi.wu-at-gmail.com/>> wrote:
>
> > 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?

My mistake; I pushed to the wrong repo. Please try again.

I see a new version, but I still see .successor().

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

As I've said before, the “ing” suffix strongly implies we're returning
(a version of) `c`, not of `i`. c.f.

Please hand me **your coat, emptying the left pocket**.

You're not going to get a pocket; you're getting a whole coat.

Quite right; didn't mean to retread that. I feel the same deficiency applies to using the "form" convention, though, in that (at least as has been discussed on this list) the convention usually refers to the receiver being mutated. Thus, `c.formLocation(...)` sounds like `c` should be mutated in some way.

One way out that I can think of is looking to good ol' Objective-C conventions. By this I mean that, in my mind, shorter method names like `str.appending(...)` are derived by omitting redundant words from longer ancestral names such as `str.stringByAppendingString(...)`. In this particular case, certain words are not redundant and perhaps we should just bravely put back those words that are necessary to clarify.

That is, if this were Objective-C, we'd have something like "indexByAdvancingIndex". You're quite right that we can't use just "advancing" because it implies returning a version of the receiver. We've tried "index", but then it conflicts with another method "index". Now there's renaming "index" to "location", even though it returns a thing of type Index... Aren't the most succinct but still accurate method names instead: `c.indexByAdvancing(i, ...)` and `c.advanceIndex(&i, ...)`? [Incidentally, `c.advance` might read like c is being advanced.]

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

the limit label is the least of my concerns here :-)

That said, orthogonally, I feel like many `limitedBy` labels can be simplified to `limit` :)

> > On Mon, Apr 25, 2016 at 1:24 PM, Dave Abrahams via swift-evolution > > > <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> >
> > on Wed Apr 20 2016, Chris Lattner <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> >
> > > On Apr 10, 2016, at 2:41 PM, Chris Lattner > > > > <clattner@apple.com <mailto: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> 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 <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 <mailto:swift-evolution@swift.org>
> > https://lists.swift.org/mailman/listinfo/swift-evolution
> >
>
> --
> Dave
>

--
Dave

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

dabrahams · April 13, 2016, 9:26pm

Yes, I totally agree that `Collection.subscript(_: Index)` should not
be Optional.

But I think that index-manipulation methods like `successor(of:)` are
a different story. It is normal and expected that, when you alter an
index, you will occasionally hit the boundaries of the
collection. There certainly are cases where you know a particular
index manipulation is safe, but most index manipulations need to be
guarded by something like:

  while index < collection.endIndex {
    let nextIndex = collection.successor(of: index)
    …
    index = nextIndex
  }

I disagree that this should be considered a “guard.” You are testing
against another index—a basic feature of what makes something an index.
It's probably a bit more likely that this other index is at the end of
the collection, but it might not be. For example, look at the algorithm
for reversing a collection in place:

  extension BidirectionalCollection where Self : MutableCollection {
    mutating func reverse() {
      if isEmpty { return } // early exit eliminates a branch in the loop
      var i = startIndex
      var j = predecessor(of: endIndex)
      while i < j {
        swap(&self[i], &self[j])
        formSuccessor(&i)
        formPredecessor(&j)
      }
    }
  }

[Why isn't this in the stdlib?! Someone file a bug and write a proposal,
quick!]

In these cases, it would be better if the `successor(of:)` method was
designed in a way that acknowledged and encapsulated the bounds check
that is usually required when it is used:

  while let nextIndex = collection.successor(of: index) {
    …
    index = nextIndex
  }

I disagree; it doesn't make sense that I should have to check for nil
when I'm not really interested in the end of the collection as in my
example above. Many other nontrivial algorithms will have the same
characteristic. If all you need is to loop through indices to the end,
there are lots of ways to do it.

Looking closer, what you've got here is actually a *highly* unusual
case, where you want a pair of indices that you want to always point to
successive elements. I do not know of any algorithm that would use this
except maybe bubblesort, and frankly I cannot see any reason to change
the standard library to support it. Am I missing something?

Given the difficulties of statically detecting index invalidation, I
totally agree that (as you discussed in a section I've snipped) we
can't statically prove indexes are safe. But we can, at the point
where we generate an index, easily check if that index is *currently*
valid. And it's something that most callers will have to do anyway if
we don't do it ourselves.

I really disagree with the assertion that most callers will need to do
this. It certainly isn't a normal thing to do in any algorithm I know
of. If you think I'm wrong (not unheard of!), I suggest you code up the
method you've requested and try to apply it in actual code that
manipulates indices, and show us how it improved the code.

We will change the index(_:stepsFrom:limitedBy:) overload to return
an optional, and we will see what other implications it has, and how
it fits into the rest of the system.

I'm glad to hear you'll evaluate this option, and I think it can give
us both what we want from this API.

I think having the most high-level operations incorporate bounds
checks, while the lower-level ones don't, is a good compromise.

That may be the pattern you discern in Swift's bounds checks, but I just
want to be very clear that it's not a criterion we use to make the
determination. I would love it if we had a more systematic way to make
the choice to insert bounds checks or not, but for now it remains
something of an art, trying to balance usability and performance
concerns.

If we encourage people to use `index(_:stepsFrom:limitedBy:)` unless
they know what they're doing, naïve clients will get an implicit
bounds check, while sophisticated, speed-sensitive clients can use
methods like `successor(of:)` which require them to check bounds
manually.

It's not a bounds check. There are lots of ways to pass a limit that's
outside the bounds of the collection, and you can pass a limit that's in
the opposite direction from the offset. If they happen to pass the
collection's endIndex and a positive offset, it degenerates to a bounds
check, but that's not what this method is for.

I will encourage people to use high-level algorithms where possible, so
they're not doing index manipulations directly. Anyone doing low-level
index manipulations is probably implementing an algorithm, and I'll
encourage them to do whatever will be most efficient, and then test the
algorithm on some very strict models of Collection, that check
everything. You can find some of these in the StdlibUnittest library in
the swift source tree.

···

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

(There might even be a case for offering bounds-checked
`successor(of:limitedBy:)` and `predecessor(of:limitedBy:)` methods to
give people bounds-checked alternatives to all three.)

Thanks again, Brent.

Thank you!

--
Dave

gribozavr · April 18, 2016, 6:16am

This is an interesting concept! Would this work with slices? You
should be able to use indices from slices with the base collection,
and vice-versa (when indices are in range).

Dmitri

···

On Sun, Apr 17, 2016 at 11:14 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:

Preventing indices of one collection being used by another collection can be done by using path dependent types like in Scala.

Then 'i' would have type a.Index (where 'a' is the instance!) and therefore b[i] would not typecheck as it would require an index of type b.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>*/

trs · April 18, 2016, 9:33am

Good point!

I just tried the following on scastie.org:

class Coll(val elements: List[Int]) {

case class Index(val value: Int)

def firstIndex: Index = Index(0)

def get(index: Index) = elements(index.value)

def slice(start: Index) = new Slice(start.value)

  class Slice(val start: Int) {
    def firstIndex: Index = Index(start)
    def get(index: Index) = elements(index.value)
  }

}

object Main extends App {

val a = new Coll(List(1, 2, 3))
val b = new Coll(List(1, 2, 3))

val i = a.firstIndex

a.get(i)
// b.get(i) // type error

val s = a.slice(a.firstIndex)
s.get(a.firstIndex) // allowed!

  val s2 = b.slice(b.firstIndex)
  s2.get(b.firstIndex)
  // s2.get(a.firstIndex) // type error
}

So it seems that having Slice as nested class (which has an implicit reference to the collection instance) results in a slice to have the same index type as its parent collection, so that it indeed works as intended.

Now the question is whether this would fit the design of slices in Swift and whether/how path dependent types would fit nicely into the design of Swift.

-Thorsten

···

Am 18.04.2016 um 08:16 schrieb Dmitri Gribenko <gribozavr@gmail.com>:

On Sun, Apr 17, 2016 at 11:14 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Preventing indices of one collection being used by another collection can be done by using path dependent types like in Scala.

Then 'i' would have type a.Index (where 'a' is the instance!) and therefore b[i] would not typecheck as it would require an index of type b.Index

This is an interesting concept! Would this work with slices? You
should be able to use indices from slices with the base collection,
and vice-versa (when indices are in range).

plx · April 18, 2016, 11:04pm

Again you're encoding “I'm at the end” in the index, which as we've
agreed does not work.

If nothing else, it works—and seems natural—for linked lists.

Sorry; if I’d remembered this elementary example sooner I would’ve lead with it.

I’ll point it out then be completely done.

So one special index value “moves automatically as the collection changes” and
all others do not. Doesn't seem like an advantage to me. It's easy to
imagine having subtle bugs due to this difference.

Again, if you implement a textbook linked-list under collections-move-indices, the natural representation for the indices is arguably `ListNode<T>?` (or whatever), wherein you use `nil` for the end index.

As a consequence, at least in this scenario you wind up with the semantics/behavior sketched previously for `endIndex`.

No further reply is needed; thank you for sharing your insight.

···

On Apr 18, 2016, at 4:52 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

hlovatt · April 18, 2016, 10:25pm

A Scala like new-Iterator pattern, using path-dependent typing, might be:

struct Range<T: Comparable> { ... }
func ..< <T: Comparable>(lowest: T, highest: T) { ... }

struct Array<T>: Collection {

static struct Iterator { ... } // Note static

...

func next(iterator: inout Iterator) -> Element? { ... }

subscript(range: Range<Int>) -> [E] { ... }

}

With new iterators, Scala style, the following is legal:

let a = [Int]()
let b = [Int]()
let i = a.Iterator() // Create an instance of an inner type, type
associated with an instance of its outer type
let aE = a.next(&i)
let r = 1 ..< 2
let aS = a[r]
let bS = b[r] // OK since `r` is not associated with `a` because `Range` is
not nested within `Array`

but not

let bE = b.next(&i) // Type error because `i` is associated with `a` not `b`

The type `Iterator` is static because it does not capture the enclosing
type instance, the enclosing type instance, `a` in the example, is solely
used for typing. Non-static inner types capture an instance of their outer
type.

The other interesting pattern using inner types is old-style
iterators, conventional external iterators:

struct Array<T>: Collection {

struct Iterator { ... } // Note *not* static, therefore captures outer
instance when created

...

}

With external iterators, Scala style, the following is legal:

let a = [Int]()
let i = a.Iterator() // Create an instance of an inner type, *capturing*
and type associating with an instance of its outer type
let aE = i.next()

Whilst this pattern in use is very similar to what Swift currently does it
is a lot easier to optimise because an escape analysis can tell if the
capture of `a` by `i` needs to increment the reference counting or not. The
compiler knows that `i` has captured `a` which allows this optimisation. I
*think* that Java's JVM's escape analysis does this optimisation.

Assuming that Swift could optimise inner types then this would allow
retention of traditional external iterators.

···

On Monday, 18 April 2016, Dmitri Gribenko via swift-evolution < swift-evolution@swift.org> wrote:

On Sun, Apr 17, 2016 at 11:14 PM, Thorsten Seitz <tseitz42@icloud.com> > wrote:
> Preventing indices of one collection being used by another collection
can be done by using path dependent types like in Scala.
>
> Then 'i' would have type a.Index (where 'a' is the instance!) and
therefore b[i] would not typecheck as it would require an index of type
b.Index

This is an interesting concept! Would this work with slices? You
should be able to use indices from slices with the base collection,
and vice-versa (when indices are in range).

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>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

trs · April 19, 2016, 8:01am

This should still be possible:

val a: Collection<T> = ...
val indices: List<a.Index> = ...

As 'a.Index' is just a normal type it should be possible to declare a collection containing elements of just that type (I haven't tried it out, yet, though, as I currently have no access to a development machine).

-Thorsten

···

Am 18.04.2016 um 23:54 schrieb Dave Abrahams via swift-evolution <swift-evolution@swift.org>:

on Sat Apr 16 2016, Thorsten Seitz <swift-evolution@swift.org> wrote:

Am 15.04.2016 um 23:19 schrieb Dmitri Gribenko via swift-evolution <swift-evolution@swift.org>:

On Fri, Apr 15, 2016 at 1:30 PM, Stephan Tolksdorf <st@quanttec.com> wrote:

On 2016-04-12 Dmitri Gribenko via swift-evolution wrote:

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.

The proposal requires Index values to be Comparable. Does that mean that
indices from different collection instances should be comparable i.e. have a
strict total order?

No, comparing indices from unrelated instances produces unspecified
results (incl. traps).

Path dependent types as used in Scala would allow making this
distinction type safe (see
http://docs.scala-lang.org/tutorials/tour/inner-classes or
http://danielwestheide.com/blog/2013/02/13/the-neophytes-guide-to-scala-part-13-path-dependent-types.html\)
by allowing the index type to be rooted at the instance.

Wouldn't that also rule out useful designs, as in those where indices
into one collection are stored in another?

dabrahams · April 26, 2016, 9:46pm

I prefer the index() method name for this purpose, but I wonder if we might want
to consider overloads for forward/backward, since not all indexes are
bidirectional (or at least, not efficiently so), for example:

index(_ index:Index, advancedBy:Index.Distance) -> Index
index(_ index:Index, reversedBy:Index.Distance) -> Index // Only declared where
Self.Index : BidirectionalIndexType?

But yeah, everything related to index manipulation should be doable from some
variant of .index() I think.

I agree and have updated the proposal accordingly.

github.com

apple/swift-evolution/blob/main/proposals/0065-collections-move-indices.md

# A New Model for Collections and Indices

* Proposal: [SE-0065](0065-collections-move-indices.md)
* Authors: [Dmitri Gribenko](https://github.com/gribozavr), [Dave Abrahams](https://github.com/dabrahams), [Maxim Moiseev](https://github.com/moiseev)
* Review Manager: [Chris Lattner](https://github.com/lattner)
* Status: **Implemented (Swift 3)**
* Decision Notes: [Rationale](https://forums.swift.org/t/accepted-se-0065-a-new-model-for-collections/2371), [Swift-evolution thread](https://forums.swift.org/t/rfc-new-collections-model-collections-advance-indices/1643)
* Implementation: [apple/swift#2108](https://github.com/apple/swift/pull/2108)
* Previous Revisions: [1](https://github.com/apple/swift-evolution/blob/21fac2e8034e79e4f44c1c8799808fc8cba83395/proposals/0065-collections-move-indices.md), [2](https://github.com/apple/swift-evolution/blob/1a821cf7ccbdf1d7566e9ce2e991bdd835ba3b7d/proposals/0065-collections-move-indices.md), [3](https://github.com/apple/swift-evolution/blob/d44c3e7c189ba39ddf8a914ae8b78b71f88fdcdf/proposals/0065-collections-move-indices.md), [4](https://github.com/apple/swift-evolution/blob/57639040dc08d2f0b16d9bda527db069589b58d1/proposals/0065-collections-move-indices.md)

## Summary

We propose a new model for `Collection`s wherein responsibility for
index traversal is moved from the index to the collection itself.  For
example, instead of writing `i.successor()`, one would write
`c.index(after: i)`.  We also propose the following changes as a
consequence of the new model:

* A collection's `Index` can be any `Comparable` type.
* The distinction between intervals and ranges disappears, leaving

This file has been truncated. show original

    Yes, I too find the naming confusing. I think the method should contain
    'index', either in the prefix or as a parameter label, so if you searched
    through Collection’s methods you’d be able to find every one that was to do
    with indexes.

    Sorry to suggest more ideas, but here is a theoretical API with index in the
    prefix: (the noun is ‘index’)

    func index(_ index: Index, offsetBy n: IndexDistance) -> Index

    func index(_ index: Index, offsetBy n: IndexDistance, limitedBy limit:
    Index) -> Index

    func formIndex(_ index: inout Index, offsetBy n: IndexDistance)

    func formIndex(_ index: inout Index, offsetBy n: IndexDistance, limitedBy
    limit: Index)

    And here is one within a parameter: (the verb is ‘offset’)

    func offsetted(index: Index, by n: IndexDistance) -> Index

    func offsetted(index: Index, by n: IndexDistance, limitedBy limit: Index) ->
    Index

    func offset(index: inout Index, offsetBy n: IndexDistance)

    func offset(index: inout Index, offsetBy n: IndexDistance, limitedBy limit:
    Index)

    Patrick Smith

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

            My mistake; I pushed to the wrong repo. Please try again.

        I see a new version, but I still see .successor().

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

            As I've said before, the “ing” suffix strongly implies we're
            returning
            (a version of) `c`, not of `i`. c.f.

            Please hand me **your coat, emptying the left pocket**.

            You're not going to get a pocket; you're getting a whole coat.

        Quite right; didn't mean to retread that. I feel the same deficiency
        applies to using the "form" convention, though, in that (at least as has
        been discussed on this list) the convention usually refers to the
        receiver being mutated. Thus, `c.formLocation(...)` sounds like `c`
        should be mutated in some way.

        One way out that I can think of is looking to good ol' Objective-C
        conventions. By this I mean that, in my mind, shorter method names like
        `str.appending(...)` are derived by omitting redundant words from longer
        ancestral names such as `str.stringByAppendingString(...)`. In this
        particular case, certain words are not redundant and perhaps we should
        just bravely put back those words that are necessary to clarify.

        That is, if this were Objective-C, we'd have something like
        "indexByAdvancingIndex". You're quite right that we can't use just
        "advancing" because it implies returning a version of the receiver.
        We've tried "index", but then it conflicts with another method "index".
        Now there's renaming "index" to "location", even though it returns a
        thing of type Index... Aren't the most succinct but still accurate
        method names instead: `c.indexByAdvancing(i, ...)` and `c.advanceIndex
        (&i, ...)`? [Incidentally, `c.advance` might read like c is being
        advanced.]

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

            the limit label is the least of my concerns here :-)

        That said, orthogonally, I feel like many `limitedBy` labels can be
        simplified to `limit` :)

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

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

Thanks!

···

on Tue Apr 26 2016, Haravikk <swift-evolution@swift.org> wrote:

    On 26 Apr 2016, at 08:49, Patrick Smith via swift-evolution > <swift-evolution@swift.org> wrote:
    On Apr 26 2016, at 11:52 am, Xiaodi Wu via swift-evolution > <swift-evolution@swift.org> wrote:
        On Mon, Apr 25, 2016 at 8:25 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 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:

--
Dave

plx · April 13, 2016, 11:05pm

In these cases, it would be better if the `successor(of:)` method was
designed in a way that acknowledged and encapsulated the bounds check
that is usually required when it is used:

  while let nextIndex = collection.successor(of: index) {
    …
    index = nextIndex
  }

I disagree; it doesn't make sense that I should have to check for nil
when I'm not really interested in the end of the collection as in my
example above. Many other nontrivial algorithms will have the same
characteristic. If all you need is to loop through indices to the end,
there are lots of ways to do it.

Looking closer, what you've got here is actually a *highly* unusual
case, where you want a pair of indices that you want to always point to
successive elements. I do not know of any algorithm that would use this
except maybe bubblesort, and frankly I cannot see any reason to change
the standard library to support it. Am I missing something?

Enumerating adjacent pairs from a sequence has its uses; when it’s a collection you can make the "adjacent pairs” thing itself a collection, and a pair of adjacent indices from the source collection makes a natural choice for the non-end-index indices.

In this case I agree the language doesn’t need to change; just write the generic “adjacent pairs” thingy and then use it like so:

// if you *really* wanted values:
for (left,right) in collection.adjacentPairs() { …

// if you *did* actually want indices;
for (leftIndex,rightIndex) in collection.indices.adjacentPairs() {

…but all the uses I make of it for higher-level things than e.g. “algorithms” in the STL sense.

···

On Apr 13, 2016, at 4:26 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Tue Apr 12 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

Given the difficulties of statically detecting index invalidation, I
totally agree that (as you discussed in a section I've snipped) we
can't statically prove indexes are safe. But we can, at the point
where we generate an index, easily check if that index is *currently*
valid. And it's something that most callers will have to do anyway if
we don't do it ourselves.

I really disagree with the assertion that most callers will need to do
this. It certainly isn't a normal thing to do in any algorithm I know
of. If you think I'm wrong (not unheard of!), I suggest you code up the
method you've requested and try to apply it in actual code that
manipulates indices, and show us how it improved the code.

We will change the index(_:stepsFrom:limitedBy:) overload to return
an optional, and we will see what other implications it has, and how
it fits into the rest of the system.

I'm glad to hear you'll evaluate this option, and I think it can give
us both what we want from this API.

I think having the most high-level operations incorporate bounds
checks, while the lower-level ones don't, is a good compromise.

That may be the pattern you discern in Swift's bounds checks, but I just
want to be very clear that it's not a criterion we use to make the
determination. I would love it if we had a more systematic way to make
the choice to insert bounds checks or not, but for now it remains
something of an art, trying to balance usability and performance
concerns.

If we encourage people to use `index(_:stepsFrom:limitedBy:)` unless
they know what they're doing, naïve clients will get an implicit
bounds check, while sophisticated, speed-sensitive clients can use
methods like `successor(of:)` which require them to check bounds
manually.

It's not a bounds check. There are lots of ways to pass a limit that's
outside the bounds of the collection, and you can pass a limit that's in
the opposite direction from the offset. If they happen to pass the
collection's endIndex and a positive offset, it degenerates to a bounds
check, but that's not what this method is for.

I will encourage people to use high-level algorithms where possible, so
they're not doing index manipulations directly. Anyone doing low-level
index manipulations is probably implementing an algorithm, and I'll
encourage them to do whatever will be most efficient, and then test the
algorithm on some very strict models of Collection, that check
everything. You can find some of these in the StdlibUnittest library in
the swift source tree.

(There might even be a case for offering bounds-checked
`successor(of:limitedBy:)` and `predecessor(of:limitedBy:)` methods to
give people bounds-checked alternatives to all three.)

Thanks again, Brent.

Thank you!

--
Dave

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