Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
79.69% covered (warning)
79.69%
51 / 64
71.43% covered (warning)
71.43%
10 / 14
 CRAP
0.00% covered (danger)
0.00%
0 / 1
DiffMatrix
79.69% covered (warning)
79.69%
51 / 64
71.43% covered (warning)
71.43%
10 / 14
 28.83
0.00% covered (danger)
0.00%
0 / 1
 __construct
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 calculateDiffMatrix
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 3
 getDiffOps
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
 3
 hasDiffOps
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
 3
 getEditCountByRow
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
 2
 getEditCountByCol
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
 2
 getIndicesOfRemovedItems
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
 getIndicesOfAddedItems
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
 getIndicesOfMaxEdits
50.00% covered (danger)
50.00%
6 / 12
0.00% covered (danger)
0.00%
0 / 1
 2.50
 getTopIndicesByEdits
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 2
 getCols
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
 1
 getNormalizer
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
 1
 zeroArray
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
 2
 __toString
0.00% covered (danger)
0.00%
0 / 5
0.00% covered (danger)
0.00%
0 / 1
 6
1<?php
2/**
3 * WikiLambda DiffMatrix utility class to compute differences
4 * between two lists with different number of items.
5 *
6 * @file
7 * @ingroup Extensions
8 * @copyright 2020– Abstract Wikipedia team; see AUTHORS.txt
9 * @license MIT
10 */
11
12namespace MediaWiki\Extension\WikiLambda\Diff;
13
14use Diff\DiffOp\Diff\Diff;
15use Diff\DiffOp\DiffOp;
16
17class DiffMatrix {
18
19    /** @var array Matrix with all the DiffOps found for every combination of old and new items. */
20    private $diffMatrix = [];
21
22    /** @var array Matrix with all the DiffOps count for every combination of old and new items. */
23    private $diffCountMatrix = [];
24
25    /** @var array List of sums of edit counts for every row. */
26    private $editCountByRow;
27
28    /** @var array List of sums of edit counts for every column. */
29    private $editCountByCol;
30
31    /**
32     * Creates a DiffMatrix object between an array of old values and an array of new values.
33     * This class also exposes utilities to operate on row and col edit counts and find items
34     * that have been deleted, added or changed positions.
35     *
36     * @param ZObjectDiffer $zObjectDiffer injected ZObjectDiffer to calculate diff between list items
37     * @param array $oldArray
38     * @param array $newArray
39     */
40    public function __construct(
41        private readonly ZObjectDiffer $zObjectDiffer,
42        private readonly array $oldArray,
43        private readonly array $newArray
44    ) {
45        $this->calculateDiffMatrix();
46    }
47
48    /**
49     * Iterates over rows and colums and generates both
50     * the matrix of DiffOps and the matrix of edit counts.
51     */
52    private function calculateDiffMatrix(): void {
53        // Initialize edit count by row and by column
54        $this->editCountByRow = $this->zeroArray( count( $this->oldArray ) );
55        $this->editCountByCol = $this->zeroArray( count( $this->newArray ) );
56
57        // For every old item...
58        for ( $i = 0; $i < count( $this->oldArray ); $i++ ) {
59            $oldItem = $this->oldArray[ $i ];
60
61            // ... we calculate its diff with every new item.
62            for ( $j = 0; $j < count( $this->newArray ); $j++ ) {
63                $newItem = $this->newArray[ $j ];
64                $itemDiff = $this->zObjectDiffer->doDiff( $oldItem, $newItem );
65                $itemEditCount = count( $itemDiff );
66
67                // We set the diff and diff count collections of this class
68                $this->diffMatrix[ $i ][ $j ] = $itemDiff;
69                $this->diffCountMatrix[ $i ][ $j ] = $itemEditCount;
70                $this->editCountByRow[ $i ] += $itemEditCount;
71                $this->editCountByCol[ $j ] += $itemEditCount;
72            }
73        }
74    }
75
76    /**
77     * Get the set of DiffOps saved in the matrix by row and column indices
78     *
79     * @param int $row
80     * @param int $col
81     * @return DiffOp
82     */
83    public function getDiffOps( int $row, int $col ): DiffOp {
84        return (
85            ( $row >= count( $this->diffMatrix ) ) ||
86            ( $col >= count( $this->diffMatrix[ $row ] ) )
87        ) ? new Diff( [] ) : $this->diffMatrix[ $row ][ $col ];
88    }
89
90    /**
91     * Whether the matrix position given by row and colum registers
92     * any diffs or not
93     *
94     * @param int $row
95     * @param int $col
96     * @return bool
97     */
98    public function hasDiffOps( int $row, int $col ): bool {
99        return (
100            ( $row >= count( $this->diffCountMatrix ) ) ||
101            ( $col >= count( $this->diffCountMatrix[ $row ] ) )
102        ) ? false : ( $this->diffCountMatrix[ $row ][ $col ] > 0 );
103    }
104
105    /**
106     * Get the set of edit counts for every row.
107     *
108     * @return int[]
109     */
110    public function getEditCountByRow(): array {
111        return $this->editCountByRow;
112    }
113
114    /**
115     * Get the set of edit counts for every column.
116     *
117     * @return int[]
118     */
119    public function getEditCountByCol(): array {
120        return $this->editCountByCol;
121    }
122
123    /**
124     * Returns the indices of the old items that were most probably deleted, by looking
125     * at the matrix's rows and finding out which one or ones are the items most distinct
126     * from their previous version.
127     *
128     * The matrix is represented by new items in their columns and old items in its
129     * rows, so when we see more columns than rows, we are calculating additions,
130     * and when we see more rows than columns, we are calculating deletions.
131     *
132     * @return int[]
133     */
134    public function getIndicesOfRemovedItems(): array {
135        $numItems = count( $this->oldArray ) - count( $this->newArray );
136        return $this->getIndicesOfMaxEdits( $this->diffCountMatrix, $numItems );
137    }
138
139    /**
140     * Returns the indices of the new items that were most probably added, by looking
141     * at the matrix's columns and finding out which ones are the items most distinct
142     * from their previous version.
143     *
144     * The matrix is represented by new items in their columns and old items in its
145     * rows, so when we see more columns than rows, we are calculating additions,
146     * and when we see more rows than columns, we are calculating deletions.
147     *
148     * @return int[]
149     */
150    public function getIndicesOfAddedItems(): array {
151        $numItems = count( $this->newArray ) - count( $this->oldArray );
152        return $this->getIndicesOfMaxEdits( $this->getCols(), $numItems );
153    }
154
155    /**
156     * Helper function to get the indices of the n highest values from a given array
157     * of vectors. When we are calculating deletions, the array of vectors will be
158     * the array of rows of the matrix. When calculating additions, the array of
159     * vectors will be the transposed, so the list of columns.
160     *
161     * Given a list of vectors, and a number of items to select (number of additions
162     * or number of deletions):
163     *
164     * 1. First, try to select the indices of the added/deleted items by excluding
165     *    vectors that contain zeroes. This is because vectors containing zeroes
166     *    signal that they are identical to an element from the old version, so
167     *    they have likely not been added or deleted (that would signal they are
168     *    duplicates).
169     *
170     * 2. If with non-zero vectors we still haven't covered the number of indices
171     *    that we need to find, we try with the rest of the vectors (those that
172     *    contain one or more zeroes). For that, we order the rows by number
173     *    of edits in descending order, and we choose those missing items
174     *    that have more edits (they are most distinct to the old version)
175     *
176     * 3. In case of a tie, we prioritize choosing those items that have a higher
177     *    index. This is so that we generally choose additions and deletions at
178     *    the tail of the list, rather than at the head.
179     *
180     * @param int[][] $vectors
181     * @param int $numItems
182     * @return array
183     */
184    private function getIndicesOfMaxEdits( array $vectors, int $numItems ): array {
185        // 1. Select indices from unseen vectors (those that don't have zeroes)
186        // array_filter() does not reindex, so we have the original indexes
187        $unseenVectors = array_filter( $vectors, static function ( array $vector ): bool {
188            return !in_array( 0, $vector, true );
189        } );
190        $unseenIndices = $this->getTopIndicesByEdits( $unseenVectors, $numItems );
191
192        // If we don't need to find any additional items added, we return the found indices
193        if ( count( $unseenIndices ) === $numItems ) {
194            return $unseenIndices;
195        }
196
197        // 2. From the other vectors (the ones containing zeroes), we need to choose n keys
198        // fill up till $numItems; we do this by getting those indexes that collect more edits.
199        $numMissing = $numItems - count( $unseenIndices );
200        $seenVectors = array_filter( $vectors, static function ( array $vector ): bool {
201            return in_array( 0, $vector, true );
202        } );
203
204        // We get the leftover from $seenIndices
205        $seenIndices = $this->getTopIndicesByEdits( $seenVectors, $numMissing );
206
207        // Merge all, and we're done
208        return [ ...$unseenIndices, ...$seenIndices ];
209    }
210
211    /**
212     * Given a map of column/row vectors (indexed by their original position),
213     * returns the indices of the $max vectors with the largest sum of edit counts.
214     * If the given vectors contains less elements than the input $max, then returns
215     * all of their indices.
216     *
217     * E.g.
218     * * given $vectors [ 4 => [1,4,2,2], 5 => [2,5,3,3] ]
219     * * with $max=1 returns [ 5 ]
220     * * with $max=3 returns [ 4, 5 ]
221     *
222     * In case of tie, get latest indexes.
223     *
224     * E.g.
225     * * given $vectors [ 4 => [1,4,2,2], 5 => [4,1,2,2] ]
226     * * with $max=1 returns [ 5 ]
227     *
228     * @param int[][] $vectors
229     * @param int $max
230     * @return int[]
231     */
232    private function getTopIndicesByEdits( array $vectors, int $max ): array {
233        // We choose those that have larger number of edits, for which we first aggregate
234        $sums = array_map( static fn ( array $vect ): int => array_sum( $vect ), $vectors );
235        // ... then we sort by values in DESC order, and in case tie, by indexes in DESC
236        // NOTE: We are intentionally adding or removing at/from the tail of the list
237        // whenever there are mixed up changes/adds/additions. Otherwise we could simply
238        // use arsort( $sums ) instead of sorting by both value and index.
239        uksort( $sums, static function ( int $idxA, int $idxB ) use ( $sums ): int {
240            $diff = $sums[$idxB] <=> $sums[$idxA];
241            return ( $diff !== 0 ) ? $diff : $idxB <=> $idxA;
242        } );
243        // ... and we slice to select max $numItems, preserve_keys=true to keep the indexes
244        $sums = array_slice( $sums, 0, $max, true );
245
246        return array_keys( $sums );
247    }
248
249    /**
250     * Returns the diff count matrix transposed as columns.
251     *
252     * E.g. Given a diffCountMatrix containing the following rows:
253     * [ [0, 2, 2],
254     *   [1, 0, 4],
255     *   [1, 5, 0] ]
256     *
257     * this method returns the transposed matrix:
258     * [ [0, 1, 1],
259     *   [2, 0, 5],
260     *   [2, 4, 0] ]
261     *
262     * @return int[][]
263     */
264    private function getCols(): array {
265        return array_map(
266            fn ( $j ) => array_column( $this->diffCountMatrix, $j ),
267            range( 0, count( $this->newArray ) - 1 )
268        );
269    }
270
271    /**
272     * Return integer that calculates the correct row or column index
273     * to access a particular matrix element depending on the items
274     * that have been removed or added in the diff.
275     *
276     * @param int[] $indices
277     * @param int $index
278     * @return int
279     */
280    public function getNormalizer( array $indices, int $index ): int {
281        return count( array_filter(
282            $indices, static function ( int $i ) use ( $index ) {
283                return ( $i < $index );
284            }
285        ) );
286    }
287
288    /**
289     * Return an array of n number of zeros. This function helps us
290     * initialize the arrays of edit count by row and by column.
291     *
292     * @param int $n
293     * @return int[]
294     */
295    private function zeroArray( int $n ): array {
296        $zeroArray = [];
297        for ( $i = 0; $i < $n; $i++ ) {
298            $zeroArray[] = 0;
299        }
300        return $zeroArray;
301    }
302
303    /**
304     * Returns a string representing the matrix of edit counts.
305     *
306     * @return string
307     */
308    public function __toString(): string {
309        $string = "";
310        foreach ( $this->diffCountMatrix as $row ) {
311            $string .= json_encode( $row );
312            $string .= "\n";
313        }
314        return $string;
315    }
316}