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

[Dmitri Gribenko]

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.

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