RangeDifferencer::findDifferences()   A
last analyzed

Complexity

Conditions 3
Paths 4

Size

Total Lines 14
Code Lines 5

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 6
CRAP Score 3

Importance

Changes 0
Metric Value
cc 3
eloc 5
nc 4
nop 3
dl 0
loc 14
ccs 6
cts 6
cp 1
crap 3
rs 10
c 0
b 0
f 0
1
<?php
2
/**
3
 * (c) Steve Nebes <[email protected]>
4
 *
5
 * For the full copyright and license information, please view the LICENSE
6
 * file that was distributed with this source code.
7
 */
8
9
declare(strict_types=1);
10
11
namespace SN\DaisyDiff\RangeDifferencer;
12
13
use SN\DaisyDiff\RangeDifferencer\Core\LCSSettings;
14
15
/**
16
 * A RangeDifferencer finds the differences between two or three RangeComparatorInterfaces.
17
 *
18
 * To use the differencer, clients provide an RangeComparatorInterface that breaks their input data into a sequence of
19
 * comparable entities. The differencer returns the differences among these sequences as an array of RangeDifference
20
 * objects (findDifferences methods). Every RangeDifference represents a single kind of difference and the corresponding
21
 * ranges of the underlying comparable entities in the left, right, and optionally ancestor sides.
22
 *
23
 * Alternatively, the findRanges methods not only return objects for the differing ranges but for non-differing ranges
24
 * too.
25
 *
26
 * The algorithm used is an objectified version of one described in: A File Comparison Program, by Webb Miller and
27
 * Eugene W. Myers, Software Practice and Experience, Vol. 15, Nov. 1985.
28
 */
29
final class RangeDifferencer
30
{
31
    /**
32
     * Prevent class instantiation.
33
     *
34
     * @codeCoverageIgnore
35
     */
36
    private function __construct()
37
    {
38
    }
39
40
    /**
41
     * Finds the differences between two RangeComparatorInterfaces. The differences are returned as an array of
42
     * RangeDifferences. If no differences are detected an empty array is returned.
43
     *
44
     * @param RangeComparatorInterface $left
45
     * @param RangeComparatorInterface $right
46
     * @param LCSSettings              $settings
47
     * @return RangeDifference[]
48
     */
49 72
    public static function findDifferences(
50
        RangeComparatorInterface $left,
51
        RangeComparatorInterface $right,
52
        ?LCSSettings $settings = null
53
    ): array {
54 72
        if (null === $settings) {
55 56
            $settings = new LCSSettings();
56
        }
57
58 72
        if (!$settings->isUseGreedyMethod()) {
59 63
            return OldDifferencer::findDifferences($left, $right);
60
        }
61
62 10
        return RangeComparatorLCS::findDifferences($left, $right, $settings);
63
    }
64
65
    /**
66
     * Finds the differences among three RangeComparatorInterfaces. The differences are returned as a list of
67
     * RangeDifferences. If no differences are detected an empty list is returned. If the ancestor range comparator is
68
     * null, a two-way comparison is performed.
69
     *
70
     * @param RangeComparatorInterface $ancestor
71
     * @param RangeComparatorInterface $left
72
     * @param RangeComparatorInterface $right
73
     * @param LCSSettings              $settings
74
     * @return RangeDifference[]
75
     */
76 7
    public static function findDifferences3(
77
        RangeComparatorInterface $ancestor,
78
        RangeComparatorInterface $left,
79
        RangeComparatorInterface $right,
80
        ?LCSSettings $settings = null
81
    ): array {
82 7
        $leftAncestorScript = null;
83 7
        $rightAncestorScript = self::findDifferences($ancestor, $right, $settings);
84
85 7
        if (!empty($rightAncestorScript)) {
86 6
            $leftAncestorScript = self::findDifferences($ancestor, $left, $settings);
87
        }
88
89 7
        if (empty($leftAncestorScript) || empty($rightAncestorScript)) {
90 1
            return [];
91
        }
92
93 6
        $myIter = new DifferencesIterator($rightAncestorScript);
94 6
        $yourIter = new DifferencesIterator($leftAncestorScript);
95
96
        // Prime array with a sentinel.
97 6
        $diff3 = [];
98 6
        $diff3[] = new RangeDifference(RangeDifference::ERROR);
99
100
        // Combine the two-way edit scripts into one.
101 6
        while (null !== $myIter->getDifference() || null !== $yourIter->getDifference()) {
102 6
            $myIter->removeAll();
103 6
            $yourIter->removeAll();
104
105
            // Take the next diff that is closer to the start.
106 6
            if (null === $myIter->getDifference()) {
107
                $startThread = $yourIter;
108 6
            } elseif (null === $yourIter->getDifference()) {
109
                $startThread = $myIter;
110
            } else {
111
                // Not at end of both scripts take the lowest range.
112 6
                if ($myIter->getDifference()->getLeftStart() <= $yourIter->getDifference()->getLeftStart()) {
113 6
                    $startThread = $myIter;
114
                } else {
115
                    $startThread = $yourIter;
116
                }
117
            }
118
119 6
            $changeRangeStart = $startThread->getDifference()->getLeftStart();
120 6
            $changeRangeEnd = $startThread->getDifference()->getLeftEnd();
121 6
            $startThread->next();
122
123
            // Check for overlapping changes with other thread merge overlapping changes with this range.
124 6
            $other = $startThread->other($myIter, $yourIter);
125
126 6
            while (null !== $other->getDifference() && $other->getDifference()->getLeftStart() <= $changeRangeEnd) {
127 6
                $newMax = $other->getDifference()->getLeftEnd();
128 6
                $other->next();
129
130 6
                if ($newMax >= $changeRangeEnd) {
131 5
                    $changeRangeEnd = $newMax;
132 5
                    $other = $other->other($myIter, $yourIter);
133
                }
134
            }
135
136 6
            $diff3[] = self::createRangeDifference3(
137 6
                $myIter, $yourIter, $diff3,
138 6
                $right, $left,
139 6
                $changeRangeStart, $changeRangeEnd);
140
        }
141
142
        // Remove sentinel, the first item in the array.
143 6
        \array_shift($diff3);
144
145 6
        return $diff3;
146
    }
147
148
    /**
149
     * @param RangeComparatorInterface $left
150
     * @param RangeComparatorInterface $right
151
     * @param LCSSettings|null         $settings
152
     * @return RangeDifference[]
153
     */
154 3
    public static function findRanges(
155
        RangeComparatorInterface $left,
156
        RangeComparatorInterface $right,
157
        ?LCSSettings $settings = null
158
    ): array {
159 3
        $in = self::findDifferences($left, $right, $settings);
160 3
        $out = [];
161
162 3
        $mStart = 0;
163 3
        $yStart = 0;
164
165 3
        for ($i = 0, $iMax = \count($in); $i < $iMax; $i++) {
166 3
            $es = $in[$i];
167 3
            $rd = new RangeDifference(RangeDifference::NOCHANGE,
168 3
                $mStart, $es->getRightStart() - $mStart,
169 3
                $yStart, $es->getLeftStart() - $yStart);
170
171 3
            if ($rd->getMaxLength() !== 0) {
172 3
                $out[] = $rd;
173
            }
174
175 3
            $out[] = $es;
176
177 3
            $mStart = $es->getRightEnd();
178 3
            $yStart = $es->getLeftEnd();
179
        }
180
181 3
        $rd = new RangeDifference(RangeDifference::NOCHANGE,
182 3
            $mStart, $right->getRangeCount() - $mStart,
183 3
            $yStart, $left->getRangeCount() - $yStart);
184
185 3
        if ($rd->getMaxLength() > 0) {
186 3
            $out[] = $rd;
187
        }
188
189 3
        return $out;
190
    }
191
192
    /**
193
     * @param RangeComparatorInterface $ancestor
194
     * @param RangeComparatorInterface $left
195
     * @param RangeComparatorInterface $right
196
     * @param LCSSettings|null         $settings
197
     * @return RangeDifference[]
198
     */
199 1
    public static function findRanges3(
200
        RangeComparatorInterface $ancestor,
201
        RangeComparatorInterface $left,
202
        RangeComparatorInterface $right,
203
        ?LCSSettings $settings = null
204
    ): array {
205 1
        $in = self::findDifferences3($ancestor, $left, $right, $settings);
206 1
        $out = [];
207
208 1
        $mStart = 0;
209 1
        $yStart = 0;
210 1
        $aStart = 0;
211
212 1
        for ($i = 0, $iMax = \count($in); $i < $iMax; $i++) {
213 1
            $es = $in[$i];
214 1
            $rd = new RangeDifference(RangeDifference::NOCHANGE,
215 1
                $mStart, $es->getRightStart() - $mStart,
216 1
                $yStart, $es->getLeftStart() - $yStart,
217 1
                $aStart, $es->getAncestorStart() - $aStart);
218
219 1
            if ($rd->getMaxLength() > 0) {
220 1
                $out[] = $rd;
221
            }
222
223 1
            $out[] = $es;
224
225 1
            $mStart = $es->getRightEnd();
226 1
            $yStart = $es->getLeftEnd();
227 1
            $aStart = $es->getAncestorEnd();
228
        }
229
230 1
        $rd = new RangeDifference(RangeDifference::NOCHANGE,
231 1
            $mStart, $right->getRangeCount() - $mStart,
232 1
            $yStart, $left->getRangeCount() - $yStart,
233 1
            $aStart, $ancestor->getRangeCount() - $aStart);
234
235 1
        if ($rd->getMaxLength() > 0) {
236 1
            $out[] = $rd;
237
        }
238
239 1
        return $out;
240
    }
241
242
    /**
243
     * @param DifferencesIterator      $myIter
244
     * @param DifferencesIterator      $yourIter
245
     * @param array                    $diff3
246
     * @param RangeComparatorInterface $right
247
     * @param RangeComparatorInterface $left
248
     * @param int                      $changeRangeStart
249
     * @param int                      $changeRangeEnd
250
     * @return RangeDifference
251
     */
252 6
    private static function createRangeDifference3(
253
        DifferencesIterator $myIter,
254
        DifferencesIterator $yourIter,
255
        array &$diff3,
256
        RangeComparatorInterface $right,
257
        RangeComparatorInterface $left,
258
        int $changeRangeStart = 0,
259
        int $changeRangeEnd = 0
260
    ): RangeDifference {
261 6
        $kind = RangeDifference::ERROR;
262
263
        /** @var RangeDifference $last */
264 6
        $last = $diff3[\count($diff3) - 1];
265
266
        // At least one range array must be non-empty.
267 6
        \assert($myIter->getCount() > 0 || $yourIter->getCount() > 0);
268
269
        // Find corresponding lines to fChangeRangeStart/End in right and left.
270 6
        if (0 === $myIter->getCount()) {
271
            // Only left changed.
272
            $rightStart = $changeRangeStart - $last->getAncestorEnd() + $last->getRightEnd();
273
            $rightEnd = $changeRangeEnd - $last->getAncestorEnd() + $last->getRightEnd();
274
            $kind = RangeDifference::LEFT;
275
        } else {
276
            /** @var RangeDifference[] $range */
277 6
            $range = $myIter->getRange();
278 6
            $f = $range[0];
279 6
            $l = $range[\count($range) - 1];
280 6
            $rightStart = $changeRangeStart - $f->getLeftStart() + $f->getRightStart();
281 6
            $rightEnd = $changeRangeEnd - $l->getLeftEnd() + $l->getRightEnd();
282
        }
283
284 6
        if (0 === $yourIter->getCount()) {
285
            // Only right changed.
286
            $leftStart = $changeRangeStart - $last->getAncestorEnd() + $last->getLeftEnd();
287
            $leftEnd = $changeRangeEnd - $last->getAncestorEnd() + $last->getLeftEnd();
288
            $kind = RangeDifference::RIGHT;
289
        } else {
290
            /** @var RangeDifference[] $range */
291 6
            $range = $yourIter->getRange();
292 6
            $f = $range[0];
293 6
            $l = $range[\count($range) - 1];
294 6
            $leftStart = $changeRangeStart - $f->getLeftStart() + $f->getRightStart();
295 6
            $leftEnd = $changeRangeEnd - $l->getLeftEnd() + $l->getRightEnd();
296
        }
297
298 6
        if (RangeDifference::ERROR === $kind) {
299
            // Overlapping change (conflict).
300 6
            if (self::rangeSpansEqual(
301 6
                $right, $rightStart, $rightEnd - $rightStart, $left, $leftStart, $leftEnd - $leftStart)) {
302 1
                $kind = RangeDifference::ANCESTOR;
303
            } else {
304 5
                $kind = RangeDifference::CONFLICT;
305
            }
306
        }
307
308 6
        return new RangeDifference(
309 6
            $kind,
310 6
            $rightStart, $rightEnd - $rightStart,
311 6
            $leftStart, $leftEnd - $leftStart,
312 6
            $changeRangeStart, $changeRangeEnd - $changeRangeStart);
313
    }
314
315
    /**
316
     * @param RangeComparatorInterface $right
317
     * @param int                      $rightStart
318
     * @param int                      $rightLen
319
     * @param RangeComparatorInterface $left
320
     * @param int                      $leftStart
321
     * @param int                      $leftLen
322
     * @return bool
323
     */
324 6
    private static function rangeSpansEqual(
325
        RangeComparatorInterface $right,
326
        int $rightStart,
327
        int $rightLen,
328
        RangeComparatorInterface $left,
329
        int $leftStart,
330
        int $leftLen
331
    ): bool {
332 6
        if ($rightLen === $leftLen) {
333 2
            for ($i = 0; $i < $rightLen; $i++) {
334 2
                if (!self::rangesEqual($right, $rightStart + $i, $left, $leftStart + $i)) {
335 1
                    break;
336
                }
337
            }
338
339 2
            if ($i === $rightLen) {
340 1
                return true;
341
            }
342
        }
343
344 5
        return false;
345
    }
346
347
    /**
348
     * @param RangeComparatorInterface $a
349
     * @param int                      $ai
350
     * @param RangeComparatorInterface $b
351
     * @param int                      $bi
352
     * @return bool
353
     */
354 2
    private static function rangesEqual(
355
        RangeComparatorInterface $a,
356
        int $ai,
357
        RangeComparatorInterface $b,
358
        int $bi
359
    ): bool {
360 2
        return $a->rangesEqual($ai, $b, $bi);
361
    }
362
}
363