Tobias Gritschacher has uploaded a new change for review. https://gerrit.wikimedia.org/r/85845
Change subject: (bug 54319) Introduce order-aware array comparer ...................................................................... (bug 54319) Introduce order-aware array comparer Change-Id: Ie60368122fd1db5b1d80107ab017be0686dfd05e --- M Diff.classes.php A src/ArrayComparer/StrategicOrderedArrayComparer.php A src/differ/CallbackOrderedListDiffer.php A tests/phpunit/ArrayComparer/StrategicOrderedArrayComparerTest.php A tests/phpunit/differ/CallbackOrderedListDifferTest.php 5 files changed, 702 insertions(+), 0 deletions(-) git pull ssh://gerrit.wikimedia.org:29418/mediawiki/extensions/Diff refs/changes/45/85845/1 diff --git a/Diff.classes.php b/Diff.classes.php index 9ec55da..8a3da0b 100644 --- a/Diff.classes.php +++ b/Diff.classes.php @@ -18,6 +18,7 @@ 'Diff\ArrayComparer\ArrayComparer' => 'src/ArrayComparer/ArrayComparer.php', 'Diff\ArrayComparer\NativeArrayComparer' => 'src/ArrayComparer/NativeArrayComparer.php', 'Diff\ArrayComparer\StrategicArrayComparer' => 'src/ArrayComparer/StrategicArrayComparer.php', + 'Diff\ArrayComparer\StrategicOrderedArrayComparer' => 'src/ArrayComparer/StrategicOrderedArrayComparer.php', 'Diff\ArrayComparer\StrictArrayComparer' => 'src/ArrayComparer/StrictArrayComparer.php', 'Diff\Comparer\CallbackComparer' => 'src/Comparer/CallbackComparer.php', @@ -25,6 +26,7 @@ 'Diff\Comparer\ValueComparer' => 'src/Comparer/ValueComparer.php', 'Diff\CallbackListDiffer' => 'src/differ/CallbackListDiffer.php', + 'Diff\CallbackOrderedListDiffer' => 'src/differ/CallbackOrderedListDiffer.php', 'Diff\Differ' => 'src/differ/Differ.php', 'Diff\ListDiffer' => 'src/differ/ListDiffer.php', 'Diff\MapDiffer' => 'src/differ/MapDiffer.php', diff --git a/src/ArrayComparer/StrategicOrderedArrayComparer.php b/src/ArrayComparer/StrategicOrderedArrayComparer.php new file mode 100644 index 0000000..930cf0a --- /dev/null +++ b/src/ArrayComparer/StrategicOrderedArrayComparer.php @@ -0,0 +1,78 @@ +<?php + +namespace Diff\ArrayComparer; + +use Diff\Comparer\ValueComparer; +use RuntimeException; + +/** + * Computes the difference between two ordered arrays by comparing elements with + * a ValueComparer. + * + * Quantity matters: [42, 42] and [42] are different + * Order matters: [42, 43] and [43, 42] are different + * + * @since 0.8 + * + * @licence GNU GPL v2+ + * @author Jeroen De Dauw < jeroended...@gmail.com > + * @author Tobias Gritschacher < tobias.gritschac...@wikimedia.de > + */ +class StrategicOrderedArrayComparer implements ArrayComparer { + + protected $valueComparer; + + public function __construct( ValueComparer $valueComparer ) { + $this->valueComparer = $valueComparer; + } + + /** + * @see ArrayComparer::diffArrays + * + * @since 0.8 + * + * @param array $arrayOne + * @param array $arrayTwo + * + * @return array + */ + public function diffArrays( array $arrayOne, array $arrayTwo ) { + $notInTwo = array(); + + foreach ( $arrayOne as $valueOffset => $element ) { + if ( !$this->arraySearch( $element, $arrayTwo, $valueOffset ) ) { + $notInTwo[] = $element; + continue; + } + + unset( $arrayTwo[$valueOffset] ); + } + + return $notInTwo; + } + + /** + * @since 0.8 + * + * @param string|int $needle + * @param array $haystack + * @param int|string $valueOffset + * + * @return bool + * @throws RuntimeException + */ + protected function arraySearch( $needle, array $haystack, $valueOffset ) { + if ( array_key_exists( $valueOffset, $haystack )) { + $areEqual = $this->valueComparer->valuesAreEqual( $needle, $haystack[$valueOffset] ); + + if ( !is_bool( $areEqual ) ) { + throw new RuntimeException( 'ValueComparer returned a non-boolean value' ); + } + + return $areEqual; + } + + return false; + } + +} diff --git a/src/differ/CallbackOrderedListDiffer.php b/src/differ/CallbackOrderedListDiffer.php new file mode 100644 index 0000000..edbf7fe --- /dev/null +++ b/src/differ/CallbackOrderedListDiffer.php @@ -0,0 +1,56 @@ +<?php + +namespace Diff; + +use Diff\ArrayComparer\StrategicOrderedArrayComparer; +use Diff\Comparer\CallbackComparer; + +/** + * Differ that looks at the order of the values and the values of the arrays. + * Values are compared via callback. + * + * Quantity matters: [42, 42] and [42] are different + * Order matters: [42, 43] and [43, 42] are different + * + * @since 0.8 + * + * @licence GNU GPL v2+ + * @author Jeroen De Dauw < jeroended...@gmail.com > + * @author Tobias Gritschacher < tobias.gritschac...@wikimedia.de > + */ +class CallbackOrderedListDiffer implements Differ { + + /** + * @since 0.8 + * + * @var ListDiffer + */ + protected $differ = null; + + /** + * Constructor. + * + * @since 0.8 + * + * @param callable $comparisonCallback + */ + public function __construct( $comparisonCallback ) { + $this->differ = new ListDiffer( new StrategicOrderedArrayComparer( new CallbackComparer( $comparisonCallback ) ) ); + } + + /** + * @see Differ::doDiff + * + * @since 0.8 + * + * @param array $oldValues The first array + * @param array $newValues The second array + * + * @return DiffOp[] + */ + public function doDiff( array $oldValues, array $newValues ) { + $diffOps = $this->differ->doDiff( $oldValues, $newValues ); + return $diffOps; + } + +} diff --git a/tests/phpunit/ArrayComparer/StrategicOrderedArrayComparerTest.php b/tests/phpunit/ArrayComparer/StrategicOrderedArrayComparerTest.php new file mode 100644 index 0000000..02c7d1a --- /dev/null +++ b/tests/phpunit/ArrayComparer/StrategicOrderedArrayComparerTest.php @@ -0,0 +1,271 @@ +<?php + +namespace Diff\Tests\ArrayComparer; + +use Diff\ArrayComparer\ArrayComparer; +use Diff\ArrayComparer\StrategicOrderedArrayComparer; +use Diff\Tests\DiffTestCase; + +/** + * @covers Diff\ArrayComparer\StrategicOrderedArrayComparer + * + * @file + * @since 0.8 + * + * @ingroup DiffTest + * + * @group Diff + * + * @licence GNU GPL v2+ + * @author Jeroen De Dauw < jeroended...@gmail.com > + * @author Tobias Gritschacher < tobias.gritschac...@wikimedia.de > + */ +class StrategicOrderedArrayComparerTest extends DiffTestCase { + + public function testCanConstruct() { + new StrategicOrderedArrayComparer( $this->getMock( 'Diff\Comparer\ValueComparer' ) ); + $this->assertTrue( true ); + } + + public function testDiffArraysWithComparerThatAlwaysReturnsTrue() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->any() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnValue( true ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->assertNoDifference( + $arrayComparer, + array( 0, 2, 4 ), + array( 1, 2, 9 ) + ); + + $this->assertNoDifference( + $arrayComparer, + array( 1, 2, 3 ), + array( 1, 2, 3 ) + ); + + $this->assertNoDifference( + $arrayComparer, + array( 'bah' ), + array( 'foo', 'bar', 'baz' ) + ); + + $this->assertNoDifference( + $arrayComparer, + array(), + array( 'foo', 'bar', 'baz' ) + ); + + $this->assertNoDifference( + $arrayComparer, + array(), + array() + ); + } + + protected function assertNoDifference( ArrayComparer $arrayComparer, array $arrayOne, array $arrayTwo ) { + $this->assertEquals( + array(), + $arrayComparer->diffArrays( + $arrayOne, + $arrayTwo + ) + ); + } + + public function testDiffArraysWithComparerThatAlwaysReturnsFalse() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->any() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnValue( false ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->assertAllDifferent( + $arrayComparer, + array(), + array() + ); + + $this->assertAllDifferent( + $arrayComparer, + array( 1, 2, 3 ), + array() + ); + + $this->assertAllDifferent( + $arrayComparer, + array( 1, 2, 3 ), + array( 1, 2, 3 ) + ); + + $this->assertAllDifferent( + $arrayComparer, + array(), + array( 1, 2, 3 ) + ); + } + + protected function assertAllDifferent( ArrayComparer $arrayComparer, array $arrayOne, array $arrayTwo ) { + $this->assertEquals( + $arrayOne, + $arrayComparer->diffArrays( + $arrayOne, + $arrayTwo + ) + ); + } + + public function testQuantityMattersWithReturnTrue() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->any() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnValue( true ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->assertEquals( + array( 1, 1, 1 ), + $arrayComparer->diffArrays( + array( 1, 1, 1, 1 ), + array( 1 ) + ) + ); + + $this->assertEquals( + array( 1 ), + $arrayComparer->diffArrays( + array( 1, 1, 1, 1 ), + array( 1, 1, 1 ) + ) + ); + } + + public function testQuantityMattersWithSimpleComparison() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->any() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnCallback( function( $firstValue, $secondValue ) { + return $firstValue == $secondValue; + } ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->assertEquals( + array( 1, 2, 3, 2, 5 ), + $arrayComparer->diffArrays( + array( 1, 1, 2, 3, 2, 5 ), + array( 1, 2, 3, 4 ) + ) + ); + + $this->assertEquals( + array( 1, 2 ), + $arrayComparer->diffArrays( + array( 1, 1, 1, 2, 2, 3 ), + array( 1, 1, 2, 2, 3, 3, 3 ) + ) + ); + + $this->assertEquals( + array( 3, 1, 2, 1, 1, 2 ), + $arrayComparer->diffArrays( + array( 3, 1, 2, 1, 1, 2 ), + array( 1, 3, 3, 2, 2, 3, 1 ) + ) + ); + } + + public function testOrderMattersWithSimpleComparison() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->any() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnCallback( function( $firstValue, $secondValue ) { + return $firstValue == $secondValue; + } ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->assertEquals( + array(), + $arrayComparer->diffArrays( + array( 1, 2, 3, 4, 5 ), + array( 1, 2, 3, 4, 5 ) + ) + ); + + $this->assertEquals( + array( 1, 2, 3, 4 ), + $arrayComparer->diffArrays( + array( 1, 2, 3, 4, 5 ), + array( 2, 1, 4, 3, 5 ) + ) + ); + + $this->assertEquals( + array( 1, 5 ), + $arrayComparer->diffArrays( + array( 1, 2, 3, 4, 5 ), + array( 5, 2, 3, 4, 1 ) + ) + ); + + $this->assertEquals( + array( 1, 2, 3, 4, 5 ), + $arrayComparer->diffArrays( + array( 1, 2, 3, 4, 5 ), + array( 2, 3, 4, 5 ) + ) + ); + + $this->assertEquals( + array( 1, 2, 3, 4 ), + $arrayComparer->diffArrays( + array( 1, 2, 3, 4 ), + array( 5, 1, 2, 3, 4 ) + ) + ); + } + + public function testValueComparerGetsCalledWithCorrectValues() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->once() ) + ->method( 'valuesAreEqual' ) + ->with( + $this->equalTo( 1 ), + $this->equalTo( 2 ) + ) + ->will( $this->returnValue( true ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $arrayComparer->diffArrays( + array( 1 ), + array( 2 ) + ); + } + + public function testCallbackComparisonReturningNyanCat() { + $valueComparer = $this->getMock( 'Diff\Comparer\ValueComparer' ); + + $valueComparer->expects( $this->once() ) + ->method( 'valuesAreEqual' ) + ->will( $this->returnValue( '~=[,,_,,]:3' ) ); + + $arrayComparer = new StrategicOrderedArrayComparer( $valueComparer ); + + $this->setExpectedException( 'RuntimeException' ); + + $arrayComparer->diffArrays( array( 1, '2', 'baz' ), array( 1, 'foo', '2' ) ); + } + +} diff --git a/tests/phpunit/differ/CallbackOrderedListDifferTest.php b/tests/phpunit/differ/CallbackOrderedListDifferTest.php new file mode 100644 index 0000000..a5a2f64 --- /dev/null +++ b/tests/phpunit/differ/CallbackOrderedListDifferTest.php @@ -0,0 +1,295 @@ +<?php + +namespace Diff\Tests; + +use Diff\CallbackOrderedListDiffer; +use Diff\DiffOpAdd; +use Diff\DiffOpRemove; +use Diff\Differ; + +/** + * @covers Diff\CallbackOrderedListDiffer + * + * @since 0.8 + * + * @group Diff + * @group Differ + * + * @licence GNU GPL v2+ + * @author Jeroen De Dauw < jeroended...@gmail.com > + * @author Tobias Gritschacher < tobias.gritschac...@wikimedia.de > + */ +class CallbackOrderedListDifferTest extends DiffTestCase { + + /** + * Returns those that both work for native and strict mode. + */ + protected function getCommonArgLists() { + $argLists = array(); + + $old = array(); + $new = array(); + $expected = array(); + + $argLists[] = array( $old, $new, $expected, + 'There should be no difference between empty arrays' ); + + + $old = array( 42 ); + $new = array( 42 ); + $expected = array(); + + $argLists[] = array( $old, $new, $expected, + 'There should be no difference between arrays with the same element' ); + + + $old = array( 42, 'ohi', 4.2, false ); + $new = array( 42, 'ohi', 4.2, false ); + $expected = array(); + + $argLists[] = array( $old, $new, $expected, + 'There should be no difference between arrays with the same elements' ); + + + $old = array( 42, 'ohi', 4.2, false ); + $new = array( false, 4.2, 'ohi', 42 ); + $expected = array( + new DiffOpAdd( false ), + new DiffOpAdd( 4.2 ), + new DiffOpAdd( 'ohi' ), + new DiffOpAdd( 42 ), + new DiffOpRemove( 42 ), + new DiffOpRemove( 'ohi' ), + new DiffOpRemove( 4.2 ), + new DiffOpRemove( false ) + ); + + $argLists[] = array( $old, $new, $expected, + 'Changing the order of all four elements should result in four add operations and four remove operations' ); + + + $old = array( 42, 'ohi', 4.2, false ); + $new = array( 4.2, 'ohi', 42, false ); + $expected = array( + new DiffOpAdd( 4.2 ), + new DiffOpAdd( 42 ), + new DiffOpRemove( 42 ), + new DiffOpRemove( 4.2 ), + ); + + $argLists[] = array( $old, $new, $expected, + 'Changing the order of two of four elements should result in two add operations and two remove operations' ); + + + $old = array(); + $new = array( 42 ); + $expected = array( new DiffOpAdd( 42 ) ); + + $argLists[] = array( $old, $new, $expected, + 'An array with a single element should be an add operation different from an empty array' ); + + + $old = array( 42 ); + $new = array(); + $expected = array( new DiffOpRemove( 42 ) ); + + $argLists[] = array( $old, $new, $expected, + 'An empty array should be a remove operation different from an array with one element' ); + + + $old = array( 1 ); + $new = array( 2 ); + $expected = array( new DiffOpRemove( 1 ), new DiffOpAdd( 2 ) ); + + $argLists[] = array( $old, $new, $expected, + 'Two arrays with a single different element should differ by an add and a remove op' ); + + + $old = array( 9001, 42, 1, 0 ); + $new = array( 9001, 42, 2, 0 ); + $expected = array( new DiffOpRemove( 1 ), new DiffOpAdd( 2 ) ); + + $argLists[] = array( $old, $new, $expected, + 'Two arrays with a single different element should differ by an add and a remove op + when the order of the identical elements stays the same' ); + + + $old = array( 'a', 'b', 'c' ); + $new = array( 'c', 'b', 'a', 'd' ); + $expected = array( + new DiffOpRemove( 'a' ), + new DiffOpRemove( 'c' ), + new DiffOpAdd( 'c' ), + new DiffOpAdd( 'a' ), + new DiffOpAdd( 'd' ) + ); + + $argLists[] = array( $old, $new, $expected, + 'Changing the position of two elements and adding one new element should result + in two remove ops and three add ops' ); + + + $old = array( 'a', 'b', 'c', 'd' ); + $new = array( 'b', 'a', 'c' ); + $expected = array( + new DiffOpRemove( 'a' ), + new DiffOpRemove( 'b' ), + new DiffOpRemove( 'd' ), + new DiffOpAdd( 'b' ), + new DiffOpAdd( 'a' ) + ); + + $argLists[] = array( $old, $new, $expected, + 'Changing the position of two elements and removing the last element should result + in three remove ops and two add ops' ); + + + $old = array( 'a', 'b', 'c' ); + $new = array( 'b', 'c' ); + $expected = array( + new DiffOpRemove( 'a' ), + new DiffOpRemove( 'b' ), + new DiffOpRemove( 'c' ), + new DiffOpAdd( 'b' ), + new DiffOpAdd( 'c' ) + ); + + $argLists[] = array( $old, $new, $expected, + 'Removing the first element results in remove ops for all elements and add ops for the remaining elements, + because the position of all remaining elements has changed' ); + + return $argLists; + } + + public function toDiffProvider() { + $argLists = $this->getCommonArgLists(); + + $old = array( 42, 42 ); + $new = array( 42 ); + $expected = array( new DiffOpRemove( 42 ) ); + + $argLists[] = array( $old, $new, $expected, + '[42, 42] to [42] should [rem(42)]' ); + + + $old = array( 42 ); + $new = array( 42, 42 ); + $expected = array( new DiffOpAdd( 42 ) ); + + $argLists[] = array( $old, $new, $expected, + '[42] to [42, 42] should [add(42)]' ); + + + $old = array( '42' ); + $new = array( 42 ); + $expected = array( new DiffOpRemove( '42' ), new DiffOpAdd( 42 ) ); + + $argLists[] = array( $old, $new, $expected, + '["42"] to [42] should [rem("42"), add(42)]' ); + + + $old = array( array( 1 ) ); + $new = array( array( 2 ) ); + $expected = array( new DiffOpRemove( array( 1 ) ), new DiffOpAdd( array( 2 ) ) ); + + $argLists[] = array( $old, $new, $expected, + '[[1]] to [[2]] should [rem([1]), add([2])]' ); + + + $old = array( array( 2 ) ); + $new = array( array( 2 ) ); + $expected = array(); + + $argLists[] = array( $old, $new, $expected, + '[[2]] to [[2]] should result in an empty diff' ); + + // test "soft" object comparison + $obj1 = new \stdClass(); + $obj2 = new \stdClass(); + $objX = new \stdClass(); + + $obj1->test = "Test"; + $obj2->test = "Test"; + $objX->xest = "Test"; + + $old = array( $obj1 ); + $new = array( $obj2 ); + $expected = array( ); + + $argLists[] = array( $old, $new, $expected, + 'Two arrays containing equivalent objects should result in an empty diff' ); + + $old = array( $obj1 ); + $new = array( $objX ); + $expected = array( new DiffOpRemove( $obj1 ), new DiffOpAdd( $objX ) ); + + $argLists[] = array( $old, $new, $expected, + 'Two arrays containing different objects of the same type should result in an add and a remove op.' ); + + return $argLists; + } + + /** + * @dataProvider toDiffProvider + */ + public function testDoDiff( $old, $new, $expected, $message = '' ) { + $callback = function( $foo, $bar ) { + return is_object( $foo ) ? $foo == $bar : $foo === $bar; + }; + + $this->doTestDiff( new CallbackOrderedListDiffer( $callback ), $old, $new, $expected, $message ); + } + + protected function doTestDiff( Differ $differ, $old, $new, $expected, $message ) { + $actual = $differ->doDiff( $old, $new ); + + $this->assertArrayEquals( $expected, $actual, false, false, $message ); + } + + public function testCallbackComparisonReturningFalse() { + $differ = new CallbackOrderedListDiffer( function( $foo, $bar ) { + return false; + } ); + + $actual = $differ->doDiff( array( 1, '2' ), array( 1, '2', 'foo' ) ); + + $expected = array( + new DiffOpAdd( 1 ), + new DiffOpAdd( '2' ), + new DiffOpAdd( 'foo' ), + new DiffOpRemove( 1 ), + new DiffOpRemove( '2' ), + ); + + $this->assertArrayEquals( + $expected, $actual, false, false, + 'All elements should be removed and added when comparison callback always returns false' + ); + } + + public function testCallbackComparisonReturningTrue() { + $differ = new CallbackOrderedListDiffer( function( $foo, $bar ) { + return true; + } ); + + $actual = $differ->doDiff( array( 1, '2', 'baz' ), array( 1, 'foo', '2' ) ); + + $expected = array(); + + $this->assertArrayEquals( + $expected, $actual, false, false, + 'No elements should be removed or added when comparison callback always returns true' + ); + } + + public function testCallbackComparisonReturningNyanCat() { + $differ = new CallbackOrderedListDiffer( function( $foo, $bar ) { + return '~=[,,_,,]:3'; + } ); + + $this->setExpectedException( 'RuntimeException' ); + + $differ->doDiff( array( 1, '2', 'baz' ), array( 1, 'foo', '2' ) ); + } + +} -- To view, visit https://gerrit.wikimedia.org/r/85845 To unsubscribe, visit https://gerrit.wikimedia.org/r/settings Gerrit-MessageType: newchange Gerrit-Change-Id: Ie60368122fd1db5b1d80107ab017be0686dfd05e Gerrit-PatchSet: 1 Gerrit-Project: mediawiki/extensions/Diff Gerrit-Branch: master Gerrit-Owner: Tobias Gritschacher <tobias.gritschac...@wikimedia.de> Gerrit-Reviewer: jenkins-bot _______________________________________________ MediaWiki-commits mailing list MediaWiki-commits@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits