[swift-evolution] Add ability to validate collection indices

Tue Dec 20 11:53:30 CST 2016

on Tue Dec 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

> 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.

“Immutable value type” doesn't make all that much sense in swift, since
you can always inout a var and change its value.  But your
basic point stands.

> 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.  

Because we don't want to penalize algorithms on arrays by forcing
indexing to allocate class instances.

> 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? 

Only if you care about silly things like performance ;-)

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

-- 
-Dave