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 >> <[email protected]> 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 <[email protected]> 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 <[email protected]> >>>>> wrote: >>>>>> I don't personally agree with #3, FWIW >>>>>> >>>>>> >>>>>> >>>>>>> On Dec 19, 2016, at 3:01 AM, Alexey Komnin <[email protected]> >>>>>>> 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 >>>>>>> <[email protected]> wrote: >>>>>>>> >>>>>>>>> on Fri Dec 16 2016, Daniel Vollmer <[email protected]> wrote: >>>>>>>>> >>>>>>>>> Hi, >>>>>>>>> >>>>>>>>>> On 16 Dec 2016, at 14:56, Alexey Komnin via swift-evolution >>>>>>>>>> <[email protected]> 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 >>>>>>>> [email protected] >>>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> >>>> -- >>>> -Dave >> >> -- >> -Dave >> _______________________________________________ >> swift-evolution mailing list >> [email protected] <mailto:[email protected]> >> https://lists.swift.org/mailman/listinfo/swift-evolution > <https://lists.swift.org/mailman/listinfo/swift-evolution> -- -Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
