OldDifferencer::createRangeDifferences() - Code Metrics - Inspection of "Merge pull request #10 from snebes/phpstan" - snebes/php-daisydiff - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 981639...0d07bf )

by Steve

created 2019-01-30 22:33 UTC

OldDifferencer::createRangeDifferences() B

↳ Parent: OldDifferencer

Complexity

Conditions	9
Paths	8

Size

Total Lines	54
Code Lines	34

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	30
CRAP Score	9

Importance

Changes

Metric	Value
cc	9
eloc	34
nc	8
nop	1
dl	0
loc	54
ccs	30
cts	30
cp	1
crap	9
rs	8.0555
c	0
b	0
f	0

How to fix Long Method

<?php
/**
 * (c) Steve Nebes <[email protected]>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

declare(strict_types=1);

namespace DaisyDiff\RangeDifferencer;

/**
 * The algorithm used is an objectified version of one described in: A File Comparison Program, by Webb Miller and
 * Eugene W. Myers, Software Practice and Experience, Vol. 15, Nov. 1985.
 */
final class OldDifferencer
{
    /**
     * Prevent class instantiation.
     *
     * @codeCoverageIgnore
     */
    private function __construct()
    {
    }

    /**
     * Finds the differences between two RangeComparatorInterfaces. The differences are returned as an array of
     * RangeDifferences. If no differences are detected an empty array is returned.
     *
     * @param RangeComparatorInterface $left
     * @param RangeComparatorInterface $right
     * @return RangeDifference[]
     */
    public static function findDifferences(RangeComparatorInterface $left, RangeComparatorInterface $right): array
    {
        // Assert that both RangeComparatorInterface are of the same class.
        \assert(\get_class($right) === \get_class($left));

        $rightSize = $right->getRangeCount();
        $leftSize = $left->getRangeCount();

        // Differences matrix:
        // Only the last d of each diagonal is stored, i.e., $lastDiagonal[$k] = row of d
        $diagLen = (int) (2 * \max($rightSize, $leftSize));
        $maxDiagonal = $diagLen;

        /** @var int[] The row containing the last d */
        $lastDiagonal = \array_fill(0, $diagLen + 1, 0);

        // On diagonal $k ($lastDiagonal[$k] = $row
        $origin = (int) ($diagLen / 2);

        // Script corresponding to $d[$k]
        /** @var LinkedRangeDifference[] $script */
        $script = \array_fill(0, $diagLen + 1, null);
        $row = 0;

        // Find common prefix.
        for (;$row < $rightSize && $row < $leftSize && self::rangesEqual($right, $row, $left, $row);) {
            $row++;
        }

        $lastDiagonal[$origin] = $row;
        $script[$origin] = null;

        $lower = ($row === $rightSize) ? $origin + 1 : $origin - 1;
        $upper = ($row === $leftSize) ? $origin - 1 : $origin + 1;

        if ($lower > $upper) {
            return [];
        }

        // For each value of the edit distance.
        for ($d = 1; $d <= $maxDiagonal; $d++) {
            // $d is the current edit distance.

            if ($right->skipRangeComparison($d, $maxDiagonal, $left)) {
                // This condition always returns false, so the following code is never executed.
                // It should be something we already found.
                return []; // @codeCoverageIgnore
            }

            // For each relevant diagonal (-d, -d+2, ... d-2, d)
            for ($k = $lower; $k <= $upper; $k += 2) {
                // $k is the current diagonal.
                if ($k === $origin - $d || $k !== $origin + $d && $lastDiagonal[$k + 1] >= $lastDiagonal[$k - 1]) {
                    // Move down.
                    $row = $lastDiagonal[$k + 1] + 1;
                    $edit = new LinkedRangeDifference($script[$k + 1], LinkedRangeDifference::DELETE);
                } else {
                    // Move right.
                    $row = $lastDiagonal[$k - 1];
                    $edit = new LinkedRangeDifference($script[$k - 1], LinkedRangeDifference::INSERT);
                }

                $col = $row + $k - $origin;

                $edit->setRightStart($row);
                $edit->setLeftStart($col);

                \assert($k >= 0 && $k <= $maxDiagonal);
                $script[$k] = $edit;

                // Slide down the diagonal as far as possible.
                while ($row < $rightSize && $col < $leftSize && self::rangesEqual($right, $row, $left, $col)) {
                    $row++;
                    $col++;
                }

                // Unreasonable value for diagonal index.
                \assert($k >= 0 && $k <= $maxDiagonal);
                $lastDiagonal[$k] = $row;

                if ($row === $rightSize && $col === $leftSize) {
                    return self::createRangeDifferences($script[$k]);
                }

                if ($row === $rightSize) {
                    $lower = $k + 2;
                }

                if ($col === $leftSize) {
                    $upper = $k - 2;
                }
            }

            $lower--;
            $upper++;
        }

        // Too many differences.
        throw new \RuntimeException(); // @codeCoverageIgnore
    }

    /**
     * Tests if two ranges are equal
     *
     * @param RangeComparatorInterface $a
     * @param int                      $ai
     * @param RangeComparatorInterface $b
     * @param int                      $bi
     * @return bool
     */
    private static function rangesEqual(
        RangeComparatorInterface $a,
        int $ai,
        RangeComparatorInterface $b,
        int $bi
    ): bool {
        return $a->rangesEqual($ai, $b, $bi);
    }

    /**
     * Creates a Vector of DifferencesRanges out of the LinkedRangeDifference. It coalesces adjacent changes. In
     * addition, indices are changed such that the ranges are 1) open, i.e, the end of the range is not included, and 2)
     * are zero based.
     *
     * @param LinkedRangeDifference $start
     * @return RangeDifference[]
     */
    private static function createRangeDifferences(LinkedRangeDifference $start): array
    {
        $ep = self::reverseDifferences($start);
        $result = [];

        while (null !== $ep) {
            $es = new RangeDifference(RangeDifference::CHANGE);

            if ($ep->isInsert()) {
                $es->setRightStart($ep->getRightStart() + 1);
                $es->setLeftStart($ep->getLeftStart());
                $b = $ep;

                do {
                    $ep = $ep->getNext();
                    $es->setLeftLength($es->getLeftLength() + 1);
                } while (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $b->getRightStart());
            } else {
                $es->setRightStart($ep->getRightStart());
                $es->setLeftStart($ep->getLeftStart());

                // Deleted lines.
                do {
                    $a = $ep;
                    $ep = $ep->getNext();
                    $es->setRightLength($es->getRightLength() + 1);
                } while (null !== $ep && $ep->isDelete() && $ep->getRightStart() === $a->getRightStart() + 1);

                $change = (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $a->getRightStart());

                if ($change) {
                    $b = $ep;

                    // Replacement lines.
                    do {
                        $ep = $ep->getNext();
                        $es->setLeftLength($es->getLeftLength() + 1);
                    } while (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $b->getRightStart());
                } else {
                    $es->setLeftLength(0);
                }

                // Meaning of range changes from "insert after", to "replace with".
                $es->setLeftStart($es->getLeftStart() + 1);
            }

            // The script commands are 1 based, subtract one to make them zero based.
            $es->setRightStart($es->getRightStart() - 1);
            $es->setLeftStart($es->getLeftStart() - 1);

            $result[] = $es;
        }

        return $result;
    }

    /**
     * Reverses the range differences.
     *
     * @param LinkedRangeDifference $start
     * @return LinkedRangeDifference
     */
    private static function reverseDifferences(LinkedRangeDifference $start): LinkedRangeDifference
    {
        $ahead = $start;
        $ep = null;

        while (null !== $ahead) {
            $behind = $ep;
            $ep = $ahead;
            $ahead = $ahead->getNext();
            $ep->setNext($behind);
        }

        return $ep;

    }
}


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 DaisyDiff\RangeDifferencer;
12
13		/**
14		* The algorithm used is an objectified version of one described in: A File Comparison Program, by Webb Miller and
15		* Eugene W. Myers, Software Practice and Experience, Vol. 15, Nov. 1985.
16		*/
17		final class OldDifferencer
18		{
19		/**
20		* Prevent class instantiation.
21		*
22		* @codeCoverageIgnore
23		*/
24		private function __construct()
25		{
26		}
27
28		/**
29		* Finds the differences between two RangeComparatorInterfaces. The differences are returned as an array of
30		* RangeDifferences. If no differences are detected an empty array is returned.
31		*
32		* @param RangeComparatorInterface $left
33		* @param RangeComparatorInterface $right
34		* @return RangeDifference[]
35		*/
36	33	public static function findDifferences(RangeComparatorInterface $left, RangeComparatorInterface $right): array
37		{
38		// Assert that both RangeComparatorInterface are of the same class.
39	33	\assert(\get_class($right) === \get_class($left));
40
41	33	$rightSize = $right->getRangeCount();
42	33	$leftSize = $left->getRangeCount();
43
44		// Differences matrix:
45		// Only the last d of each diagonal is stored, i.e., $lastDiagonal[$k] = row of d
46	33	$diagLen = (int) (2 * \max($rightSize, $leftSize));
47	33	$maxDiagonal = $diagLen;
48
49		/** @var int[] The row containing the last d */
50	33	$lastDiagonal = \array_fill(0, $diagLen + 1, 0);
51
52		// On diagonal $k ($lastDiagonal[$k] = $row
53	33	$origin = (int) ($diagLen / 2);
54
55		// Script corresponding to $d[$k]
56		/** @var LinkedRangeDifference[] $script */
57	33	$script = \array_fill(0, $diagLen + 1, null);
58	33	$row = 0;
59
60		// Find common prefix.
61	33	for (;$row < $rightSize && $row < $leftSize && self::rangesEqual($right, $row, $left, $row);) {
62	25	$row++;
63		}
64
65	33	$lastDiagonal[$origin] = $row;
66	33	$script[$origin] = null;
67
68	33	$lower = ($row === $rightSize) ? $origin + 1 : $origin - 1;
69	33	$upper = ($row === $leftSize) ? $origin - 1 : $origin + 1;
70
71	33	if ($lower > $upper) {
72	11	return [];
73		}
74
75		// For each value of the edit distance.
76	31	for ($d = 1; $d <= $maxDiagonal; $d++) {
77		// $d is the current edit distance.
78
79	31	if ($right->skipRangeComparison($d, $maxDiagonal, $left)) {
80		// This condition always returns false, so the following code is never executed.
81		// It should be something we already found.
82		return []; // @codeCoverageIgnore
83		}
84
85		// For each relevant diagonal (-d, -d+2, ... d-2, d)
86	31	for ($k = $lower; $k <= $upper; $k += 2) {
87		// $k is the current diagonal.
88	31	if ($k === $origin - $d \|\| $k !== $origin + $d && $lastDiagonal[$k + 1] >= $lastDiagonal[$k - 1]) {
89		// Move down.
90	29	$row = $lastDiagonal[$k + 1] + 1;
91	29	$edit = new LinkedRangeDifference($script[$k + 1], LinkedRangeDifference::DELETE);
92		} else {
93		// Move right.
94	26	$row = $lastDiagonal[$k - 1];
95	26	$edit = new LinkedRangeDifference($script[$k - 1], LinkedRangeDifference::INSERT);
96		}
97
98	31	$col = $row + $k - $origin;
99
100	31	$edit->setRightStart($row);
101	31	$edit->setLeftStart($col);
102
103	31	\assert($k >= 0 && $k <= $maxDiagonal);
104	31	$script[$k] = $edit;
105
106		// Slide down the diagonal as far as possible.
107	31	while ($row < $rightSize && $col < $leftSize && self::rangesEqual($right, $row, $left, $col)) {
108	19	$row++;
109	19	$col++;
110		}
111
112		// Unreasonable value for diagonal index.
113	31	\assert($k >= 0 && $k <= $maxDiagonal);
114	31	$lastDiagonal[$k] = $row;
115
116	31	if ($row === $rightSize && $col === $leftSize) {
117	31	return self::createRangeDifferences($script[$k]);
118		}
119
120	28	if ($row === $rightSize) {
121	14	$lower = $k + 2;
122		}
123
124	28	if ($col === $leftSize) {
125	13	$upper = $k - 2;
126		}
127		}
128
129	27	$lower--;
130	27	$upper++;
131		}
132
133		// Too many differences.
134		throw new \RuntimeException(); // @codeCoverageIgnore
135		}
136
137		/**
138		* Tests if two ranges are equal
139		*
140		* @param RangeComparatorInterface $a
141		* @param int $ai
142		* @param RangeComparatorInterface $b
143		* @param int $bi
144		* @return bool
145		*/
146	29	private static function rangesEqual(
147		RangeComparatorInterface $a,
148		int $ai,
149		RangeComparatorInterface $b,
150		int $bi
151		): bool {
152	29	return $a->rangesEqual($ai, $b, $bi);
153		}
154
155		/**
156		* Creates a Vector of DifferencesRanges out of the LinkedRangeDifference. It coalesces adjacent changes. In
157		* addition, indices are changed such that the ranges are 1) open, i.e, the end of the range is not included, and 2)
158		* are zero based.
159		*
160		* @param LinkedRangeDifference $start
161		* @return RangeDifference[]
162		*/
163	31	private static function createRangeDifferences(LinkedRangeDifference $start): array
164		{
165	31	$ep = self::reverseDifferences($start);
166	31	$result = [];
167
168	31	while (null !== $ep) {
169	31	$es = new RangeDifference(RangeDifference::CHANGE);
170
171	31	if ($ep->isInsert()) {
172	7	$es->setRightStart($ep->getRightStart() + 1);
173	7	$es->setLeftStart($ep->getLeftStart());
174	7	$b = $ep;
175
176		do {
177	7	$ep = $ep->getNext();
178	7	$es->setLeftLength($es->getLeftLength() + 1);
179	7	} while (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $b->getRightStart());
180		} else {
181	27	$es->setRightStart($ep->getRightStart());
182	27	$es->setLeftStart($ep->getLeftStart());
183
184		// Deleted lines.
185		do {
186	27	$a = $ep;
187	27	$ep = $ep->getNext();
188	27	$es->setRightLength($es->getRightLength() + 1);
189	27	} while (null !== $ep && $ep->isDelete() && $ep->getRightStart() === $a->getRightStart() + 1);
190
191	27	$change = (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $a->getRightStart());
192
193	27	if ($change) {
194	12	$b = $ep;
195
196		// Replacement lines.
197		do {
198	12	$ep = $ep->getNext();
199	12	$es->setLeftLength($es->getLeftLength() + 1);
200	12	} while (null !== $ep && $ep->isInsert() && $ep->getRightStart() === $b->getRightStart());
201		} else {
202	18	$es->setLeftLength(0);
203		}
204
205		// Meaning of range changes from "insert after", to "replace with".
206	27	$es->setLeftStart($es->getLeftStart() + 1);
207		}
208
209		// The script commands are 1 based, subtract one to make them zero based.
210	31	$es->setRightStart($es->getRightStart() - 1);
211	31	$es->setLeftStart($es->getLeftStart() - 1);
212
213	31	$result[] = $es;
214		}
215
216	31	return $result;
217		}
218
219		/**
220		* Reverses the range differences.
221		*
222		* @param LinkedRangeDifference $start
223		* @return LinkedRangeDifference
224		*/
225	31	private static function reverseDifferences(LinkedRangeDifference $start): LinkedRangeDifference
226		{
227	31	$ahead = $start;
228	31	$ep = null;
229
230	31	while (null !== $ahead) {
231	31	$behind = $ep;
232	31	$ep = $ahead;
233	31	$ahead = $ahead->getNext();
234	31	$ep->setNext($behind);
235		}
236
237	31	return $ep;
		0 ignored issues – show Bug Best Practice introduced 2019-01-16 06:39 UTC by Report Bug Copy Issue Report The expression `return $ep` could return the type `null` which is incompatible with the type-hinted return `DaisyDiff\RangeDifferencer\LinkedRangeDifference`. Consider adding an additional type-check to rule them out. Loading history...
238		}
239		}
240

snebes / php-daisydiff

Push — master ( 981639...0d07bf )

OldDifferencer::createRangeDifferences() B

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Long Method

Long Method

Duplication Side-by-Side

Filter issues like