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

[plx]

> On Apr 12, 2016, at 6:11 PM, Haravikk <swift-evolution at haravikk.me> wrote:
> 
> I’m a +1 for the proposal (but as I’ve implemented a bunch of collections recently I’m not sure I’m looking forward to having to update my code to reflect the new pattern ;)
> 
> But I’m interested by these concerns:
> 
>> On 12 Apr 2016, at 17:57, plx via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>> # 1: Relatively Unsafe, Pointer-Like Semantics
>> # 2: Index Invalidation Unrepresented In Type System 
> 
> It seems to me as though we could solve #1 by solving #2 actually; if we knew when indices were invalid, then unless we’re storing .endIndex or using .startIndex or .endIndex on an empty collection (rather than .first and .last) then there should no issues of the safety of these “pointers" anymore.

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

  protocol Collection {

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

  }
  
  extension RangeReplaceableCollection {

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

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

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

> 
> The tricky thing is how to handle #2; we can do this at run-time by having indices include a reference to their parent (or some kind of ID class), plus a copy of a state variable which the collection will use to track invalidating changes. If an index is passed to the collection with an incorrect reference then it wasn’t for that collection, and if the states don’t match then the index was invalidated. But really it’d be better if we had some way to do this at compile-time which I think is what you meant; i.e- some way for the compiler to track when an index was invalidated between being stored and being used, so that passing it into the subscript or other methods will produce a warning.
> 
> I suppose this could be done using attributes on the return values for index generating properties/methods to assign some kind of tag which other methods can then mark as having been invalidated, so that anything assigned that tag can be considered invalid by the compiler if you try to use a value stored before the invalidation. This is something that could be done afterwards I think, so hopefully shouldn’t affect the proposal itself. There’ll be limits to how far the compiler can track this though, but it could help to avoid most of the simpler mistakes at least.
> 
> It’d be interesting if the compiler would also trace that an index belongs to a collection, to prevent you accidentally using compatible ones with the wrong collection when you have several; it’s good practice to check this with preconditions, or assertions for performance, but the compiler doing it could give more useful errors/advice.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160412/628fb610/attachment.html>