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

[Dave Abrahams]

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

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

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

-- 
Dave