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

[plx]

> On Apr 12, 2016, at 10:53 PM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 
> On Tue, Apr 12, 2016 at 8:46 PM, plx via swift-evolution
> <swift-evolution at swift.org> wrote:
>> 
>> 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> 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...
>>      }
>>    }
>> 
>>  }
> 
> Hi plx,
> 
> In case of RangeReplaceableCollection, the index invalidation rules
> that we currently have in mind (but haven't documented in public
> documentation yet) imply that your fast path is always correct.

That’s good news!

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

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

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

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

  }

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

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

> 
> 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 at gmail.com>*/