19.15 Implementation correspondence
The specification follows the surviving implementation's structures, shared move objects, coordinate systems, interval cases, delayed tracking and phase order. Its algorithm listings use the corresponding C++ functions from the tested reference implementation.
| Specification | Source | Functions |
|---|---|---|
| Operations and application | Operation.cpp | Operation::Apply, ownership, copying and validation |
| Structural list operations | Structural.cpp | SplitInterval, SetNewExtractionPosition, CoalesceAdjacentIntervals |
| Elementary transformations | Transform.cpp, Algorithms.h | DualIT_ii, IT2_ii, IT_xi, ET2_ii, ET_xi, Transposeii, IT_dx |
| Dual inclusion transformation | DualIT.cpp | DualIT_xx, DualIT |
| Move tracking and transpose helpers | Transpose.cpp | Track_ETxm, Transpose_ee, TransposeConcurrent_xx_1, TransposeConcurrent_xx_2 |
| Transpose | Transpose.cpp | Transpose |
| Merge | Merge.cpp | Mergeii, Mergeii_noshift, Mergedd, Mergexx, Merge |
Differences and limitations found
The surviving implementation declared an Undo member whose body contained only a failed
assertion and a TODO. It supplied no undo algorithm, so the cleaned reference implementation omits
that member. The specification covers application, Dual IT, IT, ET, Transpose and Merge.
A source comment above deletion merging said that only the last extraction in an alias group could
be enabled. This disagreed with both the code and the representation invariant: aliases are ordered
by increasing e, and an extraction is enabled exactly when e=0. Consequently
only the first extraction can be enabled. The comment is corrected in the reference source and this
chapter consistently uses the implemented rule.
One comment in the Merge implementation says that “Transpose requires” a deletion to track from a move insertion to its extraction. The surrounding function and the executed code are Merge; this is a copied label, not a different rule. The specification states the tracking requirement as part of Merge.
The specification requires every move extraction to be paired with the same shared object in a move
insertion list. The implementation relies on that invariant, but AssertValid() checks only
that the total numbers of move insertions and extractions agree; its source contains a TODO to check
the individual pairings.
No behavioural disagreement has otherwise been found between the algorithm specified here and the surviving implementation. The stronger pairing check above is a validation omission, not a difference in the operation semantics.