[swift-evolution] Add ability to validate collection indices

Tue Dec 20 11:00:00 CST 2016

My understanding is that currently indexes are immutable value types, and that we ask the collection for new indices with some relationship to the old ones.

I know we hate reference types here in Swiftland, but why not have indices be simple classes that are immutable to everyone but the collection itself.  From the outside, since it is immutable, it should have the same semantics.  But because it is a reference type, the collection could store weak reference to all the indices it gives out.  Then when the collection mutates in a way which invalidates indices, it can mutate the internals of the indices so that they still point to the same piece of data that they always did (or gets marked as invalid in the case of delete, etc…)

Is there a horrible problem with this approach I am missing? 

Thanks,
Jon

> On Dec 20, 2016, at 5:01 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> on Tue Dec 20 2016, Alexey Komnin <interfere.work-AT-gmail.com <http://interfere.work-at-gmail.com/>> wrote:
> 
>>> Because I don't see any way to use it in correct code.  At least, none
>>> that can't be more-usefully and reliably provided by returning more
>>> index information from mutating methods.
>> 
>> Ok. I agree. All the indices must be invalidated if the collection
>> object is mutated. 
> 
> I didn't say that, and in the general case, I don't agree.  Collection
> indices really must be stable when the collection is sorted, for
> example.  It is only structure-changing operations that can invalidate
> indices, and even then that's only true for some collections and some
> operations.
> 
> Note that this means that the copy-on-write step for
> conceptually-non-structure-changing mutations may not be allowed to
> change the data structure's physical structure, if that would require
> invalidating indices.
> 
>> I just thought about making it straight and obvious how to check if
>> index is still valid for simple collections like Array. Returning
>> additional index information from mutating methods is a subtle thing,
>> because some methods do not change the object layout, for example
>> append does not change validity of indices; 
> 
> It certainly could.  Conceptually, in its most general form, a
> Collection is some kind of tree (which must be of limited depth to avoid
> violating big-O expectations, but memory limitations pretty much take
> care of that---yes, this requires a small amount of handwaving).  In its
> most general form, an index describes a path through that tree.
> Appending to an in-memory B-tree could require the allocation of a new
> root node, which changes the paths to all elements in the tree, thereby
> invalidating all indices.
> 
> To avoid this effect we'd either have to require the tree to become
> unbalanced, which is too great a big-O killer, or that it be a
> RandomAccessCollection that could be indexed by Ints, which in itself
> could hurt the performance of linear traversals.
> 
>> other methods may invalidate a lot or, even, all indices, for example,
>> replaceSubrange.
>> 
>> I just want to understand the purpose of indices and what behavior is
>> intended for them. It's unclear for me now. 
> 
> I hope the above helps.
> 
>> I just see a bunch of ways to shoot myself in the foot and looking for
>> a way to change that disposition.
> 
> The best way to do it would be to write the evolution proposal that lays
> out the general index invalidation rules and the guarantees we should
> give for the various data structures, explaining why those guarantees
> are the right ones.  If we can get the proposal passed, the issue should
> be totally clear for everyone :-)
> 
>> As I see it, the problem is: there is no way to find if index is valid
>> for collection. Obvious way of checking if index is within the
>> (startIndex..<endIndex) bounds does not work. 
>> So, I know only three possible solutions to the problem:
>> 
>> 1. provide a way to check if index is valid;
> 
> 
> There's always c.indices.contains(i), though it's potentially very
> inefficient and may not tell you what you want to know (at least, not if
> you want to know the index points to the same element you thought it
> did).
> 
> But the bigger question is, what would your program do differently if it
> discovered that an index it wanted to use was invalid with respect to a
> collection?
> 
>> 2. state in documentation that all indices of any collection become
>> invalid after each mutation; 
> 
> That's too broad; as noted above, index invalidation only relates to
> structural mutation.  We should document the minimum guarantees provided
> by all Collections and also any stronger guarantees provided by specific
> Collections.
> 
>> 3. state in documentation that accessing elements of collection via
>> index after mutation is unspecified behavior.
> 
> Definitely not; you wouldn't be able to write any interesting generic
> mutating algorithms if that were the case.
> 
>> Am I right? Did I miss something?
>> 
>> I would prefer option #1, if there are no other feasible solutions to
>> the problem.
>> 
>> Thanks.
>> - Alex Komnin
>> 
>> P.S. I just noticed that our discussion fell out of swift-evolution
>> list. Added it back.
>> 
>> On Mon, Dec 19, 2016 at 8:30 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>>> 
>>> on Mon Dec 19 2016, Alexey Komnin <interfere.work-AT-gmail.com> wrote:
>>> 
>>>>> I don't personally agree with #3, FWIW
>>>> Why? I thought it may be useful.
>>> 
>>> Because I don't see any way to use it in correct code.  At least, none
>>> that can't be more-usefully and reliably provided by returning more
>>> index information from mutating methods.
>>> 
>>>> - Alex Komnin
>>>> 
>>>> On Mon, Dec 19, 2016 at 4:20 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>>>>> I don't personally agree with #3, FWIW
>>>>> 
>>>>> 
>>>>> 
>>>>>> On Dec 19, 2016, at 3:01 AM, Alexey Komnin <interfere.work at gmail.com> wrote:
>>>>>> 
>>>>>> Ok. Through the discussion I've come to the following:
>>>>>> 
>>>>>> 1. collection invalidates all indices on any mutation as a common solution;
>>>>>> 2. collection may keep some indices valid if it is feasible;
>>>>>> 3. there are should be a way to check if index is valid;
>>>>>> 4. mutating methods should return index of inserted/replaced element.
>>>>>> 
>>>>>> Did I miss anything?
>>>>>> 
>>>>>> - Alex Komnin
>>>>>> 
>>>>>> On Mon, Dec 19, 2016 at 6:10 AM, Dave Abrahams via swift-evolution
>>>>>> <swift-evolution at swift.org> wrote:
>>>>>>> 
>>>>>>>> on Fri Dec 16 2016, Daniel Vollmer <swift-evolution at swift.org> wrote:
>>>>>>>> 
>>>>>>>> Hi,
>>>>>>>> 
>>>>>>>>> On 16 Dec 2016, at 14:56, Alexey Komnin via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>>>> 
>>>>>>>> [snip]
>>>>>>>> 
>>>>>>>>> What do you think? I feel, like we should discuss it before I
>>>>>>>>> formalize it as a proposal.
>>>>>>>> 
>>>>>>>> I think this is a fruitless attempt, as even if the indices are still valid,
>>>>>>>> they may not refer to the same elements they referenced before the mutation.
>>>>>>>> 
>>>>>>>> Of course, mutating methods should state whether the invalidate existing
>>>>>>>> indices, but I think that’s about the best that can be reasonably
>>>>>>>> done.
>>>>>>> 
>>>>>>> We can do a bit more.  For example, RangeReplaceableCollection's
>>>>>>> replaceRange should return the range in the new collection state
>>>>>>> corresponding to the elements that were replaced.
>>>>>>> 
>>>>>>> --
>>>>>>> -Dave
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> swift-evolution mailing list
>>>>>>> swift-evolution at swift.org
>>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>>> --
>>> -Dave
> 
> -- 
> -Dave
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161220/b2213a52/attachment.html>