[swift-evolution] [RFC] New collections model: collections advance indices

[Károly Lőrentey]

This looks interesting! As the author of a number of custom collection
implementations, including a rather elaborate B-tree package
(https://github.com/lorentey/BTree), it always felt strange to me that
indices are expected to be able to move around the collection on their
own, while element access has to go through by the collection. It is a
great idea to fix this asymmetry.

I’ll have to carefully read through it a couple more times and look at
the prototype branch to form a real opinion, but at first glance I
like the proposal. Here are a couple of quick thoughts, with more to
come once I had time to think about the implications in detail:

- I’m not at a great fan of the `*IndexType` protocols in Swift 2. I
  do not believe they work hard enough compared to how hard it is to
  implement them, and I welcome any change that makes them even a 
  little bit simpler for the collection writer.

- Having to call a collection method to increment an index looks
  unnatural at first glance, but I can see myself getting used to it
  in a few hours.

- I know that it isn't a new requirement, but I do dislike that
  `Indexable` specifies the complexity of index operations; this puts
  a hard constraint on custom collection design. I do understand the
  desire for concrete complexity promises on operations using
  indexes, but can't we express these instead e.g. in terms of number
  of index accesses?

- I love that there is a section with detailed guidance on designing 
  tree-based collections. It’s interesting and informative.

- My B-trees are persistent data structures, thus my nodes cannot have
  parent or sibling links. Index lookup and navigation is still O(1)
  though, as my indices contain pointers to every node on the path to
  the current element. Since I have to keep looking up these nodes
  anyway to retrieve elements and to navigate around in the tree, I
  simply decided to keep them directly in the index. B-trees are super
  shallow, so there are only a handful of nodes on any path.

- I found that the most straightforward place to implement tree
  navigation methods like `next(:)` and `advance(:by:)` is on the path
  struct that contains the actual node references. There is no reason
  I couldn't have the new collection methods simply call through to
  these path methods, though -- I am currently doing the same thing in
  the BTreeIndex type anyway.
  
- I'm using weak references inside the index, with a (seriously
  underdeveloped) index invalidation method that happens to be closer
  to #2b than #2a. I'm not happy about using weak references, but this
  seemed the most sensible thing to do. I'd love to replace them with
  `unowned(unsafe)`, and the mutation counter seems like a great idea.
  The ARC issue mentioned at the end of the proposal is rather scary,
  though -- I don't know how I would protect against that.
  
  Generators/iterators look to be safe from this issue,
  so I’ll probably optimize their path representation first. 

- For mutation, I think custom APIs often make much more sense
  than general-purpose solutions. I try to discourage use of the normal
  B-tree index for doing complex tree mutations, and I instead provide 
  a cursor construct that was designed especially for performing 
  a batch of mutations in a batch:

  https://github.com/lorentey/BTree/blob/master/Sources/BTreeCursor.swift#L295-L707 

  The cursor is like an index on steroids. It has an identity with
  mutable state on its own, and it takes unique ownership of the tree
  while it is active. This frees the cursor to disable some costly
  invariants (such as maintaining up-to-date descendant counts in each
  node). This in turn allows for convenient batch editing of elements
  in the tree, with amortized O(1) insertion and removal operations.

  The cursor's approach goes the exact opposite way of this proposal:
  not only is the collection not necessary to use the cursor, but the
  collection's value isn't even available while there is an active
  cursor on it. (This is like how
  `Array.withUnsafeMutableBufferPointer()` works.)

- I'm almost positive this has been discussed before, but what is the
  rationale behind allowing non-Int `IndexDistance`s? The distance is
  getting cast to Int in a lot of places anyway (IIRC, even the stdlib
  uses numericCasts to cut a way through it.)

    associatedtype IndexDistance : SignedIntegerType = Int

- The `Indices` associated type is intriguing. I assume it is brand new?
  It seems strange that it is allowed to hold a strong reference, but
  I’ll have to look through the prototype code to grok it.

  Superficial comment: I’m not too happy with the name. The irregular
  plural is hard on non-native English speakers, plus it seems weird
  to have both an `Index` and an `Indices` type. The `indices` property
  calls it `IndexRange` (I assume by accident); I think I like that 
  name better.

- In this declaration:

    subscript(position: Index) -> Generator.Element { get }

  I find the argument name rather unfortunate, because I've been using
  the term "position" to consistently refer to the (numerical)
  position of an element in an ordered collection, which is typically
  not the same as the element's index. Could we just quietly rename
  this to `index` or `i`? :-)


> On 2016-03-02, at 03:04, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 
> Hi,
> 
> We would like to propose a major change to how collection indices
> work.  The standard library team has discussed this idea internally
> and we wrote a prototype.  Now we think it is a viable direction to
> consider, and we are bringing it for wider public discussion.
> 
> I'm pasting the first section of the proposal below to give you a
> general idea about this change, but please read the proposal to
> understand the full details.
> 
> You can find the most up to date version of the proposal at
> https://github.com/gribozavr/swift-evolution/blob/new-collections/proposals/NNNN-collections-move-indices.md
> 
> Permalink: https://github.com/gribozavr/swift-evolution/blob/87df19a9a9d73e64a2a966b807440216a608b8ad/proposals/NNNN-collections-move-indices.md
> 
> Dmitri
> 
> ## Introduction
> 
> We are proposing a new model for collections, where indices can only be
> advanced forward or backward by the corresponding collection instance.
> Indices become opaque tokens representing collection positions, that can
> be produced and consumed by collection APIs.  This allows us to reduce
> the amount of data stored in indices to the bare minimum.
> 
> Compared to the current state, the new scheme simplifies implementation
> of non-trivial indices, and fixes concurrency issues in `Set` and
> `Dictionary` indices.  It also allows us to eliminate reference-counted
> stored properties from most indices, including non-trivial ones, like
> `Set.Index` and `Dictionary.Index`, creating more optimizable code.
> 
> Out of scope for this proposal:
> 
> * Expanding the set of concrete collections provided by the standard
>  library.
> 
> * Expanding the set of collection protocols to provide functionality
>  beyond what is already provided (for example, protocols for sorted
>  collections, queues etc.)  Discussing how other concrete collections
>  fit into the current protocol hierarchy is in scope, though.

-- 
Karoly