Indices are (wrongly?) assumed to be integers and zero-based about changeset HOT 3 CLOSED

Thanks for your comments, @ole. You make a very valid point and, as always, in a well-articulated way.

[The] Edit steps are currently always integers and always zero-based (i.e. the first index is 0). This works great for the intended main use case (table and collection view updates) because the index paths of a table or collection view are also zero-based and composed of integers.

I have toyed with the idea of supporting a generic index type (the collection’s). This would make it easy to apply table/collection view data source changes spanning multiple sections, for example, using IndexPath.

(Now, more than a year later, I still feel like a newbie when it comes to Swift and haven’t yet taken the time to fully understand the problem and possible solutions.)

Your suggestion to use the term offset where applicable is just excellent. I will do that and clarify the issue in the README.

Thanks.

from changeset.

I think even if you wanted to use the collection's generic index type, it's not going to work. Take strings as an example — or String.CharacterView, to be exact, because String doesn't conform to Collection in Swift 3 (but that will likely change again in Swift 4). When I talk about string indices in the following, I mean String.CharacterView.Index, which is typealiased to String.Index.

Say we want to compute:

Changeset.edits(from: "ABC".characters, to: "😜BD".characters)

The result should clearly be:

[replace with 😜 at offset 0, replace with D at offset 2]

(I'm using "offset" here for what the library currently calls "index".)

If we wanted to refactor the library to use the collection's index type rather than integer offsets, we run into a problem. Here's the transformation matrix:

The number before each character indicates the character's string index value. Notice that the index value of "B" in the target row is 2 and not 1, as one would perhaps expect. String indices are opaque values, but internally they currently use a UTF-16 offset to indicate the character's position in the string's storage. Since the emoji character takes up two UTF-16 units, all following characters have their index value incremented. The index with the value 1 doesn't exist in the target string. (Note that the offset of "B" from the start of the target string is still 1; that's why it's important to distinguish between index and offset.)

Now see what happens if we apply the first substitution (replace the "A" at index 0 with "😜"): Making this change invalidates the indices of all subsequent characters in the string. That is, if we have earlier obtained an index for the "C" character in the source string, it would no longer be valid after performing the first substitution (the same index now points to the "B" character; depending on the change, it may also have become entirely invalid and cause a crash if you tried to subscript the mutated with it).

It's probably possible (if difficult) to apply the current algorithm to strings using the string index type because the algorithm goes through the collections from left to right (top to bottom) and never has to consider values to the right (bottom) of the current element, but the Collection protocol makes no such guarantees. Collections are free to invalidate any existing index upon mutation. Therefore, I'm not sure it's even possible to write a generic version of the algorithm that uses the collection's index type. And even if it's possible, it may not be a good idea.

from changeset.

Closed by #39.

from changeset.