Swift accepts a common format for collection differences
SE-0240 gives ordered collections a shared representation for changes. Its acceptance separates a useful difference from a guarantee of the shortest edit script.
The difficult part of comparing two collections is deciding what the comparison promises to its callers. A shortest sequence of edits sounds attractive until finding that sequence costs too much on a large input. On January 31, Swift accepted ordered collection diffing with an explicit retreat from that guarantee. The acceptance announcement permits an algorithm that balances the quality of a difference against the work needed to compute it. That decision is the most consequential part of SE-0240.
Scott Perry and Kyle Macomber proposed a common representation for collection changes, together with operations to compute and apply them. The proposal at acceptance describes the motivation in terms of state transitions. Its examples include undo histories and sending differential content to a service. This is an accepted design for an upcoming standard-library addition. Acceptance does not mean the API is available in the released toolchain today.
A representation that several algorithms can produce
An application that stores successive collection states needs some way to describe what changed between them. Keeping both collections is sufficient to reconstruct the states, but it does not communicate individual edits. Recording callbacks during mutation gives the consumer individual events, although the producer and consumer must then agree on their ordering and meaning. SE-0240 instead proposes a value representing the complete transition.
That distinction affects ownership of the work. A producer can calculate a difference before handing it to a consumer. The consumer can inspect the same value without requiring the producer to replay a sequence of callbacks. Application code can also manufacture the representation itself. The proposed validating initializer checks that insertion offsets are unique, removal offsets are unique, and associations between complementary changes are symmetric.
I like this direction because it makes a state transition an explicit value that code can examine. Swift generally makes local reasoning about values pleasant. A collection difference extends that approach to the relationship between two states, while leaving the application responsible for deciding what those states mean.
The accepted names reflect the scope of the contract. Its function becomes difference(from:), replacing shortestEditScript(from:). Its representation becomes CollectionDifference, replacing OrderedCollectionDifference. The first rename removes a promise the implementation no longer has to satisfy. Callers can depend on obtaining a valid transformation without depending on a particular minimal sequence.
Consider an editor that displays an old list beside a replacement list. Several valid edit sequences may produce the same replacement. If a test compares the exact edit sequence, it may accidentally require one particular algorithm. A test that checks the resulting collection expresses a different requirement. The acceptance makes the second requirement the appropriate starting point unless the application itself needs stronger guarantees.
Offsets describe two different states
The proposed change enumeration has insertion and removal cases. Each carries an element and an integer offset, with an optional association to its complementary change. Removal offsets refer to positions in the original collection. Insertion offsets refer to positions in the completed collection. Those two coordinate systems explain why applying changes in arbitrary order would be incorrect.
Imagine removing elements at original offsets one and three. Removing the lower position first shifts the later element. Removing the higher position first leaves the lower offset meaningful. Insertions have the opposite useful order because their offsets describe the final state. The proposal specifies iteration through removals in descending offset order, followed by insertions in ascending order.
This ordering lets an applicator process the difference without recalculating every remaining offset after every edit. It also makes the iteration order part of the meaning of the representation. A consumer sorting changes for presentation must distinguish its display order from the order required to mutate a collection.
Integer offsets also let the representation exist independently of a particular collection instance. The proposal explains that collection indices require the collection that gives them meaning. A stored transition has a different requirement. It needs positions that another compatible collection can interpret. Reconstructing collection-specific indices remains possible when the collection is available.
There is a practical cost in representing this information explicitly. A difference carries changed elements as well as positions. It is therefore useful to think of it as a description of a transition with its own contents, rather than as a view that merely points into two collections. The January review includes questions about indices and the memory retained by elements. Those are questions about the intended lifetime of a difference as much as about its spelling.
Identity remains an application decision
The same review exposes a limitation that matters for interfaces. Two records can describe the same entity while containing different field values. A list of people, for example, might retain a person with the same identifier while changing a displayed name. Whole-value equality and entity identity answer different questions in that situation.
Several reviewers objected that a basic insertion-and-removal difference does not directly describe a row reload. Comparing complete values can make an update look like a deletion followed by an insertion. Comparing identifiers can preserve identity while omitting the information that the displayed content changed. An interface adapter still needs a policy for those content changes.
This is a useful boundary to preserve in application design. A collection library can describe positional changes without knowing which fields a screen displays. It cannot decide whether a changed timestamp warrants redrawing a row or whether a changed identifier means a different entity. Treating those decisions as separate work avoids attributing application semantics to a generic comparison operation.
I find the narrower contract reasonable, although it means the standard representation will not replace every interface-specific diffing library. A shared format is valuable even when some producers require richer comparison logic. The relevant question is whether the consumer can express its required transition using the format.
Move associations offer an example of that separation. A move can be represented through a paired removal and insertion without adding another enumeration case that every consumer must handle. Consumers interested only in rebuilding the final collection can process those edits. Consumers interested in presentation can inspect the relationship between them. The representation accommodates extra meaning without requiring every applicator to understand it.
The accepted performance compromise deserves the same interpretation. Removing the shortest-script guarantee gives the library room to choose a practical algorithm for inputs with many differences. It does not establish a new complexity guarantee for every implementation. Applications that need a canonical edit script still have a stronger requirement than the accepted API promises, and their stored data or tests need to express that requirement separately.