Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
100.00% |
28 / 28 |
|
100.00% |
2 / 2 |
CRAP | |
100.00% |
1 / 1 |
| ZObjectListDiffer | |
100.00% |
28 / 28 |
|
100.00% |
2 / 2 |
13 | |
100.00% |
1 / 1 |
| setZObjectDiffer | |
100.00% |
1 / 1 |
|
100.00% |
1 / 1 |
1 | |||
| doDiff | |
100.00% |
27 / 27 |
|
100.00% |
1 / 1 |
12 | |||
| 1 | <?php |
| 2 | /** |
| 3 | * WikiLambda ZObjectListDiffer. Implements doDiff to calculate the diff |
| 4 | * between two non-associative arrays or lists. |
| 5 | * |
| 6 | * @file |
| 7 | * @ingroup Extensions |
| 8 | * @copyright 2020– Abstract Wikipedia team; see AUTHORS.txt |
| 9 | * @license MIT |
| 10 | */ |
| 11 | |
| 12 | namespace MediaWiki\Extension\WikiLambda\Diff; |
| 13 | |
| 14 | use Diff\Differ\Differ; |
| 15 | use Diff\DiffOp\DiffOp; |
| 16 | use Diff\DiffOp\DiffOpAdd; |
| 17 | use Diff\DiffOp\DiffOpRemove; |
| 18 | use Exception; |
| 19 | |
| 20 | class ZObjectListDiffer implements Differ { |
| 21 | |
| 22 | private ZObjectDiffer $zObjectDiffer; |
| 23 | |
| 24 | /** |
| 25 | * Setter for the differ service that will calculate |
| 26 | * the diffs for every idem of the list. |
| 27 | * |
| 28 | * @param ZObjectDiffer $zObjectDiffer |
| 29 | */ |
| 30 | public function setZObjectDiffer( ZObjectDiffer $zObjectDiffer ): void { |
| 31 | $this->zObjectDiffer = $zObjectDiffer; |
| 32 | } |
| 33 | |
| 34 | /** |
| 35 | * @see Differ::doDiff |
| 36 | * |
| 37 | * Compares the difference between two Typed Lists |
| 38 | * |
| 39 | * @param array $oldArray The first array |
| 40 | * @param array $newArray The second array |
| 41 | * |
| 42 | * @throws Exception |
| 43 | * @return DiffOp[] |
| 44 | */ |
| 45 | public function doDiff( array $oldArray, array $newArray ): array { |
| 46 | // 1. Compare length of arrays |
| 47 | // 2. If the length is the same, go item by item and diff them |
| 48 | // using $this->zObjectDiffer; |
| 49 | // 3. If the length is not the same then wtf. |
| 50 | |
| 51 | $listDiff = []; |
| 52 | |
| 53 | /** |
| 54 | * TODO (T338250): According to T312259 the items in a list can be reordered. |
| 55 | * |
| 56 | * Current implementation will find diffs between the items on the |
| 57 | * same position when the two lists have identical length. |
| 58 | * |
| 59 | * If we want to find position changes and flag them as such, we |
| 60 | * should calculate the edit matrix also when the count of elements |
| 61 | * is the same in $newArray and $oldArray. |
| 62 | * |
| 63 | * This would give us some matrix edit count like the following: |
| 64 | * |
| 65 | * | 0 1 1 | |
| 66 | * | 1 1 0 | |
| 67 | * | 1 0 1 | |
| 68 | * |
| 69 | * Where the zero edits are not in the matrix diagonal. This would |
| 70 | * probably flag a couple of indexChange edits such as: |
| 71 | * |
| 72 | * [ list.1, indexChange, [1, 2] ] |
| 73 | * [ list.2, indexChange, [2, 1] ] |
| 74 | * |
| 75 | * However, this means that for equal length arrays the complexity |
| 76 | * of finding a diff would directly go from O(n) to O(n2). |
| 77 | */ |
| 78 | |
| 79 | // If $newArray and $oldArray have the same number of items, |
| 80 | // check diff one by one using ZObjectDiffer |
| 81 | if ( count( $oldArray ) === count( $newArray ) ) { |
| 82 | for ( $index = 0; $index < count( $oldArray ); $index++ ) { |
| 83 | $oldItem = $oldArray[ $index ]; |
| 84 | $newItem = $newArray[ $index ]; |
| 85 | |
| 86 | $itemDiff = $this->zObjectDiffer->doDiff( $oldItem, $newItem ); |
| 87 | |
| 88 | if ( $itemDiff->isAtomic() || ( $itemDiff->count() > 0 ) ) { |
| 89 | $listDiff[ $index ] = $itemDiff; |
| 90 | } |
| 91 | } |
| 92 | } else { |
| 93 | $matrix = new DiffMatrix( $this->zObjectDiffer, $oldArray, $newArray ); |
| 94 | |
| 95 | if ( count( $oldArray ) > count( $newArray ) ) { |
| 96 | // If $oldArray has more items than $newArray, the |
| 97 | // matrix has more rows than colums, so we need to |
| 98 | // find which rows have been deleted by finding the |
| 99 | // n ones with a larger number of edits. |
| 100 | $deletedIndices = $matrix->getIndicesOfRemovedItems(); |
| 101 | for ( $index = 0; $index < count( $oldArray ); $index++ ) { |
| 102 | if ( in_array( $index, $deletedIndices ) ) { |
| 103 | // If this is one of the deleted items, create Remove operation: |
| 104 | $listDiff[ $index ] = new DiffOpRemove( $oldArray[ $index ] ); |
| 105 | } else { |
| 106 | // If this is one of the non deleted items, add any changes |
| 107 | // available in the appropriate position of the matrix: |
| 108 | $normalizer = $matrix->getNormalizer( $deletedIndices, $index ); |
| 109 | $colIndex = $index - $normalizer; |
| 110 | if ( $matrix->hasDiffOps( $index, $colIndex ) ) { |
| 111 | $listDiff[ $index ] = $matrix->getDiffOps( $index, $colIndex ); |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | } else { |
| 116 | // If $newArray has more items than $oldArray, the |
| 117 | // matrix has more colums than rows, and we need to |
| 118 | // find which columns have been added by finding the |
| 119 | // n ones with a larger number of edits. |
| 120 | $addedIndices = $matrix->getIndicesOfAddedItems(); |
| 121 | for ( $index = 0; $index < count( $newArray ); $index++ ) { |
| 122 | if ( in_array( $index, $addedIndices ) ) { |
| 123 | // If this is one of the deleted items, create Add operation: |
| 124 | $listDiff[ $index ] = new DiffOpAdd( $newArray[ $index ] ); |
| 125 | } else { |
| 126 | // If this is one of the non deleted items, add any changes |
| 127 | // available in the appropriate position of the matrix: |
| 128 | $normalizer = $matrix->getNormalizer( $addedIndices, $index ); |
| 129 | $rowIndex = $index - $normalizer; |
| 130 | if ( $matrix->hasDiffOps( $rowIndex, $index ) ) { |
| 131 | $listDiff[ $index ] = $matrix->getDiffOps( $rowIndex, $index ); |
| 132 | } |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | } |
| 137 | return $listDiff; |
| 138 | } |
| 139 | } |