From ec037d747f48ca4e25c3de6241b5d05b452051c2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tim=20D=C3=BCsterhus?= Date: Wed, 3 Aug 2022 12:18:20 +0200 Subject: [PATCH] Add sebastian/diff composer dependency --- .../files/lib/system/api/composer.json | 1 + .../files/lib/system/api/composer.lock | 68 +++- .../system/api/composer/autoload_classmap.php | 16 + .../system/api/composer/autoload_static.php | 16 + .../lib/system/api/composer/installed.json | 69 ++++ .../lib/system/api/composer/installed.php | 9 + .../system/api/sebastian/diff/ChangeLog.md | 88 +++++ .../lib/system/api/sebastian/diff/LICENSE | 33 ++ .../lib/system/api/sebastian/diff/README.md | 202 +++++++++++ .../system/api/sebastian/diff/composer.json | 47 +++ .../system/api/sebastian/diff/src/Chunk.php | 89 +++++ .../system/api/sebastian/diff/src/Diff.php | 64 ++++ .../system/api/sebastian/diff/src/Differ.php | 327 +++++++++++++++++ .../src/Exception/ConfigurationException.php | 38 ++ .../diff/src/Exception/Exception.php | 16 + .../Exception/InvalidArgumentException.php | 14 + .../system/api/sebastian/diff/src/Line.php | 45 +++ .../LongestCommonSubsequenceCalculator.php | 18 + ...ientLongestCommonSubsequenceCalculator.php | 88 +++++ .../src/Output/AbstractChunkOutputBuilder.php | 52 +++ .../diff/src/Output/DiffOnlyOutputBuilder.php | 72 ++++ .../src/Output/DiffOutputBuilderInterface.php | 19 + .../Output/StrictUnifiedDiffOutputBuilder.php | 338 ++++++++++++++++++ .../src/Output/UnifiedDiffOutputBuilder.php | 272 ++++++++++++++ .../system/api/sebastian/diff/src/Parser.php | 110 ++++++ ...ientLongestCommonSubsequenceCalculator.php | 70 ++++ 26 files changed, 2180 insertions(+), 1 deletion(-) create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/ChangeLog.md create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/LICENSE create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/README.md create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/composer.json create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Chunk.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Diff.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Differ.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/ConfigurationException.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/Exception.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/InvalidArgumentException.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Line.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/LongestCommonSubsequenceCalculator.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOutputBuilderInterface.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/Parser.php create mode 100644 wcfsetup/install/files/lib/system/api/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php diff --git a/wcfsetup/install/files/lib/system/api/composer.json b/wcfsetup/install/files/lib/system/api/composer.json index a3e06cecdb..afb0669c18 100644 --- a/wcfsetup/install/files/lib/system/api/composer.json +++ b/wcfsetup/install/files/lib/system/api/composer.json @@ -24,6 +24,7 @@ "psr/http-server-handler": "^1.0.1", "psr/http-server-middleware": "^1.0.1", "scssphp/scssphp": "^1.10.3", + "sebastian/diff": "^4.0", "symfony/polyfill-intl-idn": "^1.26.0", "symfony/polyfill-php82": "^1.26.0" }, diff --git a/wcfsetup/install/files/lib/system/api/composer.lock b/wcfsetup/install/files/lib/system/api/composer.lock index 115a7805a8..b104bd0f50 100644 --- a/wcfsetup/install/files/lib/system/api/composer.lock +++ b/wcfsetup/install/files/lib/system/api/composer.lock @@ -4,7 +4,7 @@ "Read more about it at https://getcomposer.org/doc/01-basic-usage.md#installing-dependencies", "This file is @generated automatically" ], - "content-hash": "2043ec419034245a9686f5b51a895c3c", + "content-hash": "3c208782ee8c7c9a8a8650a3605e86fc", "packages": [ { "name": "chrisjean/php-ico", @@ -1361,6 +1361,72 @@ }, "time": "2022-07-27T15:52:39+00:00" }, + { + "name": "sebastian/diff", + "version": "4.0.4", + "source": { + "type": "git", + "url": "https://github.com/sebastianbergmann/diff.git", + "reference": "3461e3fccc7cfdfc2720be910d3bd73c69be590d" + }, + "dist": { + "type": "zip", + "url": "https://api.github.com/repos/sebastianbergmann/diff/zipball/3461e3fccc7cfdfc2720be910d3bd73c69be590d", + "reference": "3461e3fccc7cfdfc2720be910d3bd73c69be590d", + "shasum": "" + }, + "require": { + "php": ">=7.3" + }, + "require-dev": { + "phpunit/phpunit": "^9.3", + "symfony/process": "^4.2 || ^5" + }, + "type": "library", + "extra": { + "branch-alias": { + "dev-master": "4.0-dev" + } + }, + "autoload": { + "classmap": [ + "src/" + ] + }, + "notification-url": "https://packagist.org/downloads/", + "license": [ + "BSD-3-Clause" + ], + "authors": [ + { + "name": "Sebastian Bergmann", + "email": "sebastian@phpunit.de" + }, + { + "name": "Kore Nordmann", + "email": "mail@kore-nordmann.de" + } + ], + "description": "Diff implementation", + "homepage": "https://github.com/sebastianbergmann/diff", + "keywords": [ + "diff", + "udiff", + "unidiff", + "unified diff" + ], + "support": { + "issues": "https://github.com/sebastianbergmann/diff/issues", + "source": "https://github.com/sebastianbergmann/diff/tree/4.0.4" + }, + "funding": [ + { + "url": "https://github.com/sebastianbergmann", + "type": "github" + } + ], + "time": "2020-10-26T13:10:38+00:00" + }, { "name": "symfony/css-selector", "version": "v6.1.3", diff --git a/wcfsetup/install/files/lib/system/api/composer/autoload_classmap.php b/wcfsetup/install/files/lib/system/api/composer/autoload_classmap.php index b12cea6545..3c12185da8 100644 --- a/wcfsetup/install/files/lib/system/api/composer/autoload_classmap.php +++ b/wcfsetup/install/files/lib/system/api/composer/autoload_classmap.php @@ -584,6 +584,22 @@ return array( 'ScssPhp\\ScssPhp\\ValueConverter' => $vendorDir . '/scssphp/scssphp/src/ValueConverter.php', 'ScssPhp\\ScssPhp\\Version' => $vendorDir . '/scssphp/scssphp/src/Version.php', 'ScssPhp\\ScssPhp\\Warn' => $vendorDir . '/scssphp/scssphp/src/Warn.php', + 'SebastianBergmann\\Diff\\Chunk' => $vendorDir . '/sebastian/diff/src/Chunk.php', + 'SebastianBergmann\\Diff\\ConfigurationException' => $vendorDir . '/sebastian/diff/src/Exception/ConfigurationException.php', + 'SebastianBergmann\\Diff\\Diff' => $vendorDir . '/sebastian/diff/src/Diff.php', + 'SebastianBergmann\\Diff\\Differ' => $vendorDir . '/sebastian/diff/src/Differ.php', + 'SebastianBergmann\\Diff\\Exception' => $vendorDir . '/sebastian/diff/src/Exception/Exception.php', + 'SebastianBergmann\\Diff\\InvalidArgumentException' => $vendorDir . '/sebastian/diff/src/Exception/InvalidArgumentException.php', + 'SebastianBergmann\\Diff\\Line' => $vendorDir . '/sebastian/diff/src/Line.php', + 'SebastianBergmann\\Diff\\LongestCommonSubsequenceCalculator' => $vendorDir . '/sebastian/diff/src/LongestCommonSubsequenceCalculator.php', + 'SebastianBergmann\\Diff\\MemoryEfficientLongestCommonSubsequenceCalculator' => $vendorDir . '/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php', + 'SebastianBergmann\\Diff\\Output\\AbstractChunkOutputBuilder' => $vendorDir . '/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\DiffOnlyOutputBuilder' => $vendorDir . '/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\DiffOutputBuilderInterface' => $vendorDir . '/sebastian/diff/src/Output/DiffOutputBuilderInterface.php', + 'SebastianBergmann\\Diff\\Output\\StrictUnifiedDiffOutputBuilder' => $vendorDir . '/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\UnifiedDiffOutputBuilder' => $vendorDir . '/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php', + 'SebastianBergmann\\Diff\\Parser' => $vendorDir . '/sebastian/diff/src/Parser.php', + 'SebastianBergmann\\Diff\\TimeEfficientLongestCommonSubsequenceCalculator' => $vendorDir . '/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php', 'SensitiveParameter' => $vendorDir . '/symfony/polyfill-php82/Resources/stubs/SensitiveParameter.php', 'SensitiveParameterValue' => $vendorDir . '/symfony/polyfill-php82/Resources/stubs/SensitiveParameterValue.php', 'Symfony\\Component\\CssSelector\\CssSelectorConverter' => $vendorDir . '/symfony/css-selector/CssSelectorConverter.php', diff --git a/wcfsetup/install/files/lib/system/api/composer/autoload_static.php b/wcfsetup/install/files/lib/system/api/composer/autoload_static.php index defc115393..8a36befdc9 100644 --- a/wcfsetup/install/files/lib/system/api/composer/autoload_static.php +++ b/wcfsetup/install/files/lib/system/api/composer/autoload_static.php @@ -739,6 +739,22 @@ class ComposerStaticInita1f5f7c74275d47a45049a2936db1d0d 'ScssPhp\\ScssPhp\\ValueConverter' => __DIR__ . '/..' . '/scssphp/scssphp/src/ValueConverter.php', 'ScssPhp\\ScssPhp\\Version' => __DIR__ . '/..' . '/scssphp/scssphp/src/Version.php', 'ScssPhp\\ScssPhp\\Warn' => __DIR__ . '/..' . '/scssphp/scssphp/src/Warn.php', + 'SebastianBergmann\\Diff\\Chunk' => __DIR__ . '/..' . '/sebastian/diff/src/Chunk.php', + 'SebastianBergmann\\Diff\\ConfigurationException' => __DIR__ . '/..' . '/sebastian/diff/src/Exception/ConfigurationException.php', + 'SebastianBergmann\\Diff\\Diff' => __DIR__ . '/..' . '/sebastian/diff/src/Diff.php', + 'SebastianBergmann\\Diff\\Differ' => __DIR__ . '/..' . '/sebastian/diff/src/Differ.php', + 'SebastianBergmann\\Diff\\Exception' => __DIR__ . '/..' . '/sebastian/diff/src/Exception/Exception.php', + 'SebastianBergmann\\Diff\\InvalidArgumentException' => __DIR__ . '/..' . '/sebastian/diff/src/Exception/InvalidArgumentException.php', + 'SebastianBergmann\\Diff\\Line' => __DIR__ . '/..' . '/sebastian/diff/src/Line.php', + 'SebastianBergmann\\Diff\\LongestCommonSubsequenceCalculator' => __DIR__ . '/..' . '/sebastian/diff/src/LongestCommonSubsequenceCalculator.php', + 'SebastianBergmann\\Diff\\MemoryEfficientLongestCommonSubsequenceCalculator' => __DIR__ . '/..' . '/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php', + 'SebastianBergmann\\Diff\\Output\\AbstractChunkOutputBuilder' => __DIR__ . '/..' . '/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\DiffOnlyOutputBuilder' => __DIR__ . '/..' . '/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\DiffOutputBuilderInterface' => __DIR__ . '/..' . '/sebastian/diff/src/Output/DiffOutputBuilderInterface.php', + 'SebastianBergmann\\Diff\\Output\\StrictUnifiedDiffOutputBuilder' => __DIR__ . '/..' . '/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php', + 'SebastianBergmann\\Diff\\Output\\UnifiedDiffOutputBuilder' => __DIR__ . '/..' . '/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php', + 'SebastianBergmann\\Diff\\Parser' => __DIR__ . '/..' . '/sebastian/diff/src/Parser.php', + 'SebastianBergmann\\Diff\\TimeEfficientLongestCommonSubsequenceCalculator' => __DIR__ . '/..' . '/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php', 'SensitiveParameter' => __DIR__ . '/..' . '/symfony/polyfill-php82/Resources/stubs/SensitiveParameter.php', 'SensitiveParameterValue' => __DIR__ . '/..' . '/symfony/polyfill-php82/Resources/stubs/SensitiveParameterValue.php', 'Symfony\\Component\\CssSelector\\CssSelectorConverter' => __DIR__ . '/..' . '/symfony/css-selector/CssSelectorConverter.php', diff --git a/wcfsetup/install/files/lib/system/api/composer/installed.json b/wcfsetup/install/files/lib/system/api/composer/installed.json index ea0e1c2df9..8b1d66d711 100644 --- a/wcfsetup/install/files/lib/system/api/composer/installed.json +++ b/wcfsetup/install/files/lib/system/api/composer/installed.json @@ -1415,6 +1415,75 @@ }, "install-path": "../scssphp/scssphp" }, + { + "name": "sebastian/diff", + "version": "4.0.4", + "version_normalized": "4.0.4.0", + "source": { + "type": "git", + "url": "https://github.com/sebastianbergmann/diff.git", + "reference": "3461e3fccc7cfdfc2720be910d3bd73c69be590d" + }, + "dist": { + "type": "zip", + "url": "https://api.github.com/repos/sebastianbergmann/diff/zipball/3461e3fccc7cfdfc2720be910d3bd73c69be590d", + "reference": "3461e3fccc7cfdfc2720be910d3bd73c69be590d", + "shasum": "" + }, + "require": { + "php": ">=7.3" + }, + "require-dev": { + "phpunit/phpunit": "^9.3", + "symfony/process": "^4.2 || ^5" + }, + "time": "2020-10-26T13:10:38+00:00", + "type": "library", + "extra": { + "branch-alias": { + "dev-master": "4.0-dev" + } + }, + "installation-source": "dist", + "autoload": { + "classmap": [ + "src/" + ] + }, + "notification-url": "https://packagist.org/downloads/", + "license": [ + "BSD-3-Clause" + ], + "authors": [ + { + "name": "Sebastian Bergmann", + "email": "sebastian@phpunit.de" + }, + { + "name": "Kore Nordmann", + "email": "mail@kore-nordmann.de" + } + ], + "description": "Diff implementation", + "homepage": "https://github.com/sebastianbergmann/diff", + "keywords": [ + "diff", + "udiff", + "unidiff", + "unified diff" + ], + "support": { + "issues": "https://github.com/sebastianbergmann/diff/issues", + "source": "https://github.com/sebastianbergmann/diff/tree/4.0.4" + }, + "funding": [ + { + "url": "https://github.com/sebastianbergmann", + "type": "github" + } + ], + "install-path": "../sebastian/diff" + }, { "name": "symfony/css-selector", "version": "v6.1.3", diff --git a/wcfsetup/install/files/lib/system/api/composer/installed.php b/wcfsetup/install/files/lib/system/api/composer/installed.php index ef8bdda0b8..7a2205b5db 100644 --- a/wcfsetup/install/files/lib/system/api/composer/installed.php +++ b/wcfsetup/install/files/lib/system/api/composer/installed.php @@ -217,6 +217,15 @@ 'aliases' => array(), 'dev_requirement' => false, ), + 'sebastian/diff' => array( + 'pretty_version' => '4.0.4', + 'version' => '4.0.4.0', + 'reference' => '3461e3fccc7cfdfc2720be910d3bd73c69be590d', + 'type' => 'library', + 'install_path' => __DIR__ . '/../sebastian/diff', + 'aliases' => array(), + 'dev_requirement' => false, + ), 'symfony/css-selector' => array( 'pretty_version' => 'v6.1.3', 'version' => '6.1.3.0', diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/ChangeLog.md b/wcfsetup/install/files/lib/system/api/sebastian/diff/ChangeLog.md new file mode 100644 index 0000000000..9bdcc5b6d7 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/ChangeLog.md @@ -0,0 +1,88 @@ +# ChangeLog + +All notable changes are documented in this file using the [Keep a CHANGELOG](http://keepachangelog.com/) principles. + +## [4.0.4] - 2020-10-26 + +### Fixed + +* `SebastianBergmann\Diff\Exception` now correctly extends `\Throwable` + +## [4.0.3] - 2020-09-28 + +### Changed + +* Changed PHP version constraint in `composer.json` from `^7.3 || ^8.0` to `>=7.3` + +## [4.0.2] - 2020-06-30 + +### Added + +* This component is now supported on PHP 8 + +## [4.0.1] - 2020-05-08 + +### Fixed + +* [#99](https://github.com/sebastianbergmann/diff/pull/99): Regression in unified diff output of identical strings + +## [4.0.0] - 2020-02-07 + +### Removed + +* Removed support for PHP 7.1 and PHP 7.2 + +## [3.0.2] - 2019-02-04 + +### Changed + +* `Chunk::setLines()` now ensures that the `$lines` array only contains `Line` objects + +## [3.0.1] - 2018-06-10 + +### Fixed + +* Removed `"minimum-stability": "dev",` from `composer.json` + +## [3.0.0] - 2018-02-01 + +* The `StrictUnifiedDiffOutputBuilder` implementation of the `DiffOutputBuilderInterface` was added + +### Changed + +* The default `DiffOutputBuilderInterface` implementation now generates context lines (unchanged lines) + +### Removed + +* Removed support for PHP 7.0 + +### Fixed + +* [#70](https://github.com/sebastianbergmann/diff/issues/70): Diffing of arrays no longer works + +## [2.0.1] - 2017-08-03 + +### Fixed + +* [#66](https://github.com/sebastianbergmann/diff/pull/66): Restored backwards compatibility for PHPUnit 6.1.4, 6.2.0, 6.2.1, 6.2.2, and 6.2.3 + +## [2.0.0] - 2017-07-11 [YANKED] + +### Added + +* [#64](https://github.com/sebastianbergmann/diff/pull/64): Show line numbers for chunks of a diff + +### Removed + +* This component is no longer supported on PHP 5.6 + +[4.0.4]: https://github.com/sebastianbergmann/diff/compare/4.0.3...4.0.4 +[4.0.3]: https://github.com/sebastianbergmann/diff/compare/4.0.2...4.0.3 +[4.0.2]: https://github.com/sebastianbergmann/diff/compare/4.0.1...4.0.2 +[4.0.1]: https://github.com/sebastianbergmann/diff/compare/4.0.0...4.0.1 +[4.0.0]: https://github.com/sebastianbergmann/diff/compare/3.0.2...4.0.0 +[3.0.2]: https://github.com/sebastianbergmann/diff/compare/3.0.1...3.0.2 +[3.0.1]: https://github.com/sebastianbergmann/diff/compare/3.0.0...3.0.1 +[3.0.0]: https://github.com/sebastianbergmann/diff/compare/2.0...3.0.0 +[2.0.1]: https://github.com/sebastianbergmann/diff/compare/c341c98ce083db77f896a0aa64f5ee7652915970...2.0.1 +[2.0.0]: https://github.com/sebastianbergmann/diff/compare/1.4...c341c98ce083db77f896a0aa64f5ee7652915970 diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/LICENSE b/wcfsetup/install/files/lib/system/api/sebastian/diff/LICENSE new file mode 100644 index 0000000000..f22f31cf0c --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/LICENSE @@ -0,0 +1,33 @@ +sebastian/diff + +Copyright (c) 2002-2020, Sebastian Bergmann . +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + + * Neither the name of Sebastian Bergmann nor the names of his + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/README.md b/wcfsetup/install/files/lib/system/api/sebastian/diff/README.md new file mode 100644 index 0000000000..734b852de7 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/README.md @@ -0,0 +1,202 @@ +# sebastian/diff + +[![CI Status](https://github.com/sebastianbergmann/diff/workflows/CI/badge.svg)](https://github.com/sebastianbergmann/diff/actions) +[![Type Coverage](https://shepherd.dev/github/sebastianbergmann/diff/coverage.svg)](https://shepherd.dev/github/sebastianbergmann/diff) + +Diff implementation for PHP, factored out of PHPUnit into a stand-alone component. + +## Installation + +You can add this library as a local, per-project dependency to your project using [Composer](https://getcomposer.org/): + +``` +composer require sebastian/diff +``` + +If you only need this library during development, for instance to run your project's test suite, then you should add it as a development-time dependency: + +``` +composer require --dev sebastian/diff +``` + +### Usage + +#### Generating diff + +The `Differ` class can be used to generate a textual representation of the difference between two strings: + +```php +diff('foo', 'bar'); +``` + +The code above yields the output below: +```diff +--- Original ++++ New +@@ @@ +-foo ++bar +``` + +There are three output builders available in this package: + +#### UnifiedDiffOutputBuilder + +This is default builder, which generates the output close to udiff and is used by PHPUnit. + +```php +diff('foo', 'bar'); +``` + +#### StrictUnifiedDiffOutputBuilder + +Generates (strict) Unified diff's (unidiffs) with hunks, +similar to `diff -u` and compatible with `patch` and `git apply`. + +```php + true, // ranges of length one are rendered with the trailing `,1` + 'commonLineThreshold' => 6, // number of same lines before ending a new hunk and creating a new one (if needed) + 'contextLines' => 3, // like `diff: -u, -U NUM, --unified[=NUM]`, for patch/git apply compatibility best to keep at least @ 3 + 'fromFile' => null, + 'fromFileDate' => null, + 'toFile' => null, + 'toFileDate' => null, +]); + +$differ = new Differ($builder); +print $differ->diff('foo', 'bar'); +``` + +#### DiffOnlyOutputBuilder + +Output only the lines that differ. + +```php +diff('foo', 'bar'); +``` + +#### DiffOutputBuilderInterface + +You can pass any output builder to the `Differ` class as longs as it implements the `DiffOutputBuilderInterface`. + +#### Parsing diff + +The `Parser` class can be used to parse a unified diff into an object graph: + +```php +use SebastianBergmann\Diff\Parser; +use SebastianBergmann\Git; + +$git = new Git('/usr/local/src/money'); + +$diff = $git->getDiff( + '948a1a07768d8edd10dcefa8315c1cbeffb31833', + 'c07a373d2399f3e686234c4f7f088d635eb9641b' +); + +$parser = new Parser; + +print_r($parser->parse($diff)); +``` + +The code above yields the output below: + + Array + ( + [0] => SebastianBergmann\Diff\Diff Object + ( + [from:SebastianBergmann\Diff\Diff:private] => a/tests/MoneyTest.php + [to:SebastianBergmann\Diff\Diff:private] => b/tests/MoneyTest.php + [chunks:SebastianBergmann\Diff\Diff:private] => Array + ( + [0] => SebastianBergmann\Diff\Chunk Object + ( + [start:SebastianBergmann\Diff\Chunk:private] => 87 + [startRange:SebastianBergmann\Diff\Chunk:private] => 7 + [end:SebastianBergmann\Diff\Chunk:private] => 87 + [endRange:SebastianBergmann\Diff\Chunk:private] => 7 + [lines:SebastianBergmann\Diff\Chunk:private] => Array + ( + [0] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => * @covers SebastianBergmann\Money\Money::add + ) + + [1] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => * @covers SebastianBergmann\Money\Money::newMoney + ) + + [2] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => */ + ) + + [3] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 2 + [content:SebastianBergmann\Diff\Line:private] => public function testAnotherMoneyWithSameCurrencyObjectCanBeAdded() + ) + + [4] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 1 + [content:SebastianBergmann\Diff\Line:private] => public function testAnotherMoneyObjectWithSameCurrencyCanBeAdded() + ) + + [5] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => { + ) + + [6] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => $a = new Money(1, new Currency('EUR')); + ) + + [7] => SebastianBergmann\Diff\Line Object + ( + [type:SebastianBergmann\Diff\Line:private] => 3 + [content:SebastianBergmann\Diff\Line:private] => $b = new Money(2, new Currency('EUR')); + ) + ) + ) + ) + ) + ) diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/composer.json b/wcfsetup/install/files/lib/system/api/sebastian/diff/composer.json new file mode 100644 index 0000000000..cf92202ba3 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/composer.json @@ -0,0 +1,47 @@ +{ + "name": "sebastian/diff", + "description": "Diff implementation", + "keywords": ["diff", "udiff", "unidiff", "unified diff"], + "homepage": "https://github.com/sebastianbergmann/diff", + "license": "BSD-3-Clause", + "authors": [ + { + "name": "Sebastian Bergmann", + "email": "sebastian@phpunit.de" + }, + { + "name": "Kore Nordmann", + "email": "mail@kore-nordmann.de" + } + ], + "prefer-stable": true, + "config": { + "platform": { + "php": "7.3.0" + }, + "optimize-autoloader": true, + "sort-packages": true + }, + "require": { + "php": ">=7.3" + }, + "require-dev": { + "phpunit/phpunit": "^9.3", + "symfony/process": "^4.2 || ^5" + }, + "autoload": { + "classmap": [ + "src/" + ] + }, + "autoload-dev": { + "classmap": [ + "tests/" + ] + }, + "extra": { + "branch-alias": { + "dev-master": "4.0-dev" + } + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Chunk.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Chunk.php new file mode 100644 index 0000000000..16ae34f414 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Chunk.php @@ -0,0 +1,89 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +final class Chunk +{ + /** + * @var int + */ + private $start; + + /** + * @var int + */ + private $startRange; + + /** + * @var int + */ + private $end; + + /** + * @var int + */ + private $endRange; + + /** + * @var Line[] + */ + private $lines; + + public function __construct(int $start = 0, int $startRange = 1, int $end = 0, int $endRange = 1, array $lines = []) + { + $this->start = $start; + $this->startRange = $startRange; + $this->end = $end; + $this->endRange = $endRange; + $this->lines = $lines; + } + + public function getStart(): int + { + return $this->start; + } + + public function getStartRange(): int + { + return $this->startRange; + } + + public function getEnd(): int + { + return $this->end; + } + + public function getEndRange(): int + { + return $this->endRange; + } + + /** + * @return Line[] + */ + public function getLines(): array + { + return $this->lines; + } + + /** + * @param Line[] $lines + */ + public function setLines(array $lines): void + { + foreach ($lines as $line) { + if (!$line instanceof Line) { + throw new InvalidArgumentException; + } + } + + $this->lines = $lines; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Diff.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Diff.php new file mode 100644 index 0000000000..17b2084f90 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Diff.php @@ -0,0 +1,64 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +final class Diff +{ + /** + * @var string + */ + private $from; + + /** + * @var string + */ + private $to; + + /** + * @var Chunk[] + */ + private $chunks; + + /** + * @param Chunk[] $chunks + */ + public function __construct(string $from, string $to, array $chunks = []) + { + $this->from = $from; + $this->to = $to; + $this->chunks = $chunks; + } + + public function getFrom(): string + { + return $this->from; + } + + public function getTo(): string + { + return $this->to; + } + + /** + * @return Chunk[] + */ + public function getChunks(): array + { + return $this->chunks; + } + + /** + * @param Chunk[] $chunks + */ + public function setChunks(array $chunks): void + { + $this->chunks = $chunks; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Differ.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Differ.php new file mode 100644 index 0000000000..5a4d9d1024 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Differ.php @@ -0,0 +1,327 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use const PHP_INT_SIZE; +use const PREG_SPLIT_DELIM_CAPTURE; +use const PREG_SPLIT_NO_EMPTY; +use function array_shift; +use function array_unshift; +use function array_values; +use function count; +use function current; +use function end; +use function get_class; +use function gettype; +use function is_array; +use function is_object; +use function is_string; +use function key; +use function min; +use function preg_split; +use function prev; +use function reset; +use function sprintf; +use function substr; +use SebastianBergmann\Diff\Output\DiffOutputBuilderInterface; +use SebastianBergmann\Diff\Output\UnifiedDiffOutputBuilder; + +final class Differ +{ + public const OLD = 0; + + public const ADDED = 1; + + public const REMOVED = 2; + + public const DIFF_LINE_END_WARNING = 3; + + public const NO_LINE_END_EOF_WARNING = 4; + + /** + * @var DiffOutputBuilderInterface + */ + private $outputBuilder; + + /** + * @param DiffOutputBuilderInterface $outputBuilder + * + * @throws InvalidArgumentException + */ + public function __construct($outputBuilder = null) + { + if ($outputBuilder instanceof DiffOutputBuilderInterface) { + $this->outputBuilder = $outputBuilder; + } elseif (null === $outputBuilder) { + $this->outputBuilder = new UnifiedDiffOutputBuilder; + } elseif (is_string($outputBuilder)) { + // PHPUnit 6.1.4, 6.2.0, 6.2.1, 6.2.2, and 6.2.3 support + // @see https://github.com/sebastianbergmann/phpunit/issues/2734#issuecomment-314514056 + // @deprecated + $this->outputBuilder = new UnifiedDiffOutputBuilder($outputBuilder); + } else { + throw new InvalidArgumentException( + sprintf( + 'Expected builder to be an instance of DiffOutputBuilderInterface, or a string, got %s.', + is_object($outputBuilder) ? 'instance of "' . get_class($outputBuilder) . '"' : gettype($outputBuilder) . ' "' . $outputBuilder . '"' + ) + ); + } + } + + /** + * Returns the diff between two arrays or strings as string. + * + * @param array|string $from + * @param array|string $to + */ + public function diff($from, $to, LongestCommonSubsequenceCalculator $lcs = null): string + { + $diff = $this->diffToArray( + $this->normalizeDiffInput($from), + $this->normalizeDiffInput($to), + $lcs + ); + + return $this->outputBuilder->getDiff($diff); + } + + /** + * Returns the diff between two arrays or strings as array. + * + * Each array element contains two elements: + * - [0] => mixed $token + * - [1] => 2|1|0 + * + * - 2: REMOVED: $token was removed from $from + * - 1: ADDED: $token was added to $from + * - 0: OLD: $token is not changed in $to + * + * @param array|string $from + * @param array|string $to + * @param LongestCommonSubsequenceCalculator $lcs + */ + public function diffToArray($from, $to, LongestCommonSubsequenceCalculator $lcs = null): array + { + if (is_string($from)) { + $from = $this->splitStringByLines($from); + } elseif (!is_array($from)) { + throw new InvalidArgumentException('"from" must be an array or string.'); + } + + if (is_string($to)) { + $to = $this->splitStringByLines($to); + } elseif (!is_array($to)) { + throw new InvalidArgumentException('"to" must be an array or string.'); + } + + [$from, $to, $start, $end] = self::getArrayDiffParted($from, $to); + + if ($lcs === null) { + $lcs = $this->selectLcsImplementation($from, $to); + } + + $common = $lcs->calculate(array_values($from), array_values($to)); + $diff = []; + + foreach ($start as $token) { + $diff[] = [$token, self::OLD]; + } + + reset($from); + reset($to); + + foreach ($common as $token) { + while (($fromToken = reset($from)) !== $token) { + $diff[] = [array_shift($from), self::REMOVED]; + } + + while (($toToken = reset($to)) !== $token) { + $diff[] = [array_shift($to), self::ADDED]; + } + + $diff[] = [$token, self::OLD]; + + array_shift($from); + array_shift($to); + } + + while (($token = array_shift($from)) !== null) { + $diff[] = [$token, self::REMOVED]; + } + + while (($token = array_shift($to)) !== null) { + $diff[] = [$token, self::ADDED]; + } + + foreach ($end as $token) { + $diff[] = [$token, self::OLD]; + } + + if ($this->detectUnmatchedLineEndings($diff)) { + array_unshift($diff, ["#Warning: Strings contain different line endings!\n", self::DIFF_LINE_END_WARNING]); + } + + return $diff; + } + + /** + * Casts variable to string if it is not a string or array. + * + * @return array|string + */ + private function normalizeDiffInput($input) + { + if (!is_array($input) && !is_string($input)) { + return (string) $input; + } + + return $input; + } + + /** + * Checks if input is string, if so it will split it line-by-line. + */ + private function splitStringByLines(string $input): array + { + return preg_split('/(.*\R)/', $input, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY); + } + + private function selectLcsImplementation(array $from, array $to): LongestCommonSubsequenceCalculator + { + // We do not want to use the time-efficient implementation if its memory + // footprint will probably exceed this value. Note that the footprint + // calculation is only an estimation for the matrix and the LCS method + // will typically allocate a bit more memory than this. + $memoryLimit = 100 * 1024 * 1024; + + if ($this->calculateEstimatedFootprint($from, $to) > $memoryLimit) { + return new MemoryEfficientLongestCommonSubsequenceCalculator; + } + + return new TimeEfficientLongestCommonSubsequenceCalculator; + } + + /** + * Calculates the estimated memory footprint for the DP-based method. + * + * @return float|int + */ + private function calculateEstimatedFootprint(array $from, array $to) + { + $itemSize = PHP_INT_SIZE === 4 ? 76 : 144; + + return $itemSize * min(count($from), count($to)) ** 2; + } + + /** + * Returns true if line ends don't match in a diff. + */ + private function detectUnmatchedLineEndings(array $diff): bool + { + $newLineBreaks = ['' => true]; + $oldLineBreaks = ['' => true]; + + foreach ($diff as $entry) { + if (self::OLD === $entry[1]) { + $ln = $this->getLinebreak($entry[0]); + $oldLineBreaks[$ln] = true; + $newLineBreaks[$ln] = true; + } elseif (self::ADDED === $entry[1]) { + $newLineBreaks[$this->getLinebreak($entry[0])] = true; + } elseif (self::REMOVED === $entry[1]) { + $oldLineBreaks[$this->getLinebreak($entry[0])] = true; + } + } + + // if either input or output is a single line without breaks than no warning should be raised + if (['' => true] === $newLineBreaks || ['' => true] === $oldLineBreaks) { + return false; + } + + // two way compare + foreach ($newLineBreaks as $break => $set) { + if (!isset($oldLineBreaks[$break])) { + return true; + } + } + + foreach ($oldLineBreaks as $break => $set) { + if (!isset($newLineBreaks[$break])) { + return true; + } + } + + return false; + } + + private function getLinebreak($line): string + { + if (!is_string($line)) { + return ''; + } + + $lc = substr($line, -1); + + if ("\r" === $lc) { + return "\r"; + } + + if ("\n" !== $lc) { + return ''; + } + + if ("\r\n" === substr($line, -2)) { + return "\r\n"; + } + + return "\n"; + } + + private static function getArrayDiffParted(array &$from, array &$to): array + { + $start = []; + $end = []; + + reset($to); + + foreach ($from as $k => $v) { + $toK = key($to); + + if ($toK === $k && $v === $to[$k]) { + $start[$k] = $v; + + unset($from[$k], $to[$k]); + } else { + break; + } + } + + end($from); + end($to); + + do { + $fromK = key($from); + $toK = key($to); + + if (null === $fromK || null === $toK || current($from) !== current($to)) { + break; + } + + prev($from); + prev($to); + + $end = [$fromK => $from[$fromK]] + $end; + unset($from[$fromK], $to[$toK]); + } while (true); + + return [$from, $to, $start, $end]; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/ConfigurationException.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/ConfigurationException.php new file mode 100644 index 0000000000..b767b2194a --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/ConfigurationException.php @@ -0,0 +1,38 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use function get_class; +use function gettype; +use function is_object; +use function sprintf; +use Exception; + +final class ConfigurationException extends InvalidArgumentException +{ + public function __construct( + string $option, + string $expected, + $value, + int $code = 0, + Exception $previous = null + ) { + parent::__construct( + sprintf( + 'Option "%s" must be %s, got "%s".', + $option, + $expected, + is_object($value) ? get_class($value) : (null === $value ? '' : gettype($value) . '#' . $value) + ), + $code, + $previous + ); + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/Exception.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/Exception.php new file mode 100644 index 0000000000..e20d320369 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/Exception.php @@ -0,0 +1,16 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use Throwable; + +interface Exception extends Throwable +{ +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/InvalidArgumentException.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/InvalidArgumentException.php new file mode 100644 index 0000000000..846ac3fbd6 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Exception/InvalidArgumentException.php @@ -0,0 +1,14 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +class InvalidArgumentException extends \InvalidArgumentException implements Exception +{ +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Line.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Line.php new file mode 100644 index 0000000000..3596ed264c --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Line.php @@ -0,0 +1,45 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +final class Line +{ + public const ADDED = 1; + + public const REMOVED = 2; + + public const UNCHANGED = 3; + + /** + * @var int + */ + private $type; + + /** + * @var string + */ + private $content; + + public function __construct(int $type = self::UNCHANGED, string $content = '') + { + $this->type = $type; + $this->content = $content; + } + + public function getContent(): string + { + return $this->content; + } + + public function getType(): int + { + return $this->type; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/LongestCommonSubsequenceCalculator.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/LongestCommonSubsequenceCalculator.php new file mode 100644 index 0000000000..dea8fe1cb8 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/LongestCommonSubsequenceCalculator.php @@ -0,0 +1,18 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +interface LongestCommonSubsequenceCalculator +{ + /** + * Calculates the longest common subsequence of two arrays. + */ + public function calculate(array $from, array $to): array; +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php new file mode 100644 index 0000000000..0b626eaff9 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/MemoryEfficientLongestCommonSubsequenceCalculator.php @@ -0,0 +1,88 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use function array_fill; +use function array_merge; +use function array_reverse; +use function array_slice; +use function count; +use function in_array; +use function max; + +final class MemoryEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator +{ + /** + * {@inheritdoc} + */ + public function calculate(array $from, array $to): array + { + $cFrom = count($from); + $cTo = count($to); + + if ($cFrom === 0) { + return []; + } + + if ($cFrom === 1) { + if (in_array($from[0], $to, true)) { + return [$from[0]]; + } + + return []; + } + + $i = (int) ($cFrom / 2); + $fromStart = array_slice($from, 0, $i); + $fromEnd = array_slice($from, $i); + $llB = $this->length($fromStart, $to); + $llE = $this->length(array_reverse($fromEnd), array_reverse($to)); + $jMax = 0; + $max = 0; + + for ($j = 0; $j <= $cTo; $j++) { + $m = $llB[$j] + $llE[$cTo - $j]; + + if ($m >= $max) { + $max = $m; + $jMax = $j; + } + } + + $toStart = array_slice($to, 0, $jMax); + $toEnd = array_slice($to, $jMax); + + return array_merge( + $this->calculate($fromStart, $toStart), + $this->calculate($fromEnd, $toEnd) + ); + } + + private function length(array $from, array $to): array + { + $current = array_fill(0, count($to) + 1, 0); + $cFrom = count($from); + $cTo = count($to); + + for ($i = 0; $i < $cFrom; $i++) { + $prev = $current; + + for ($j = 0; $j < $cTo; $j++) { + if ($from[$i] === $to[$j]) { + $current[$j + 1] = $prev[$j] + 1; + } else { + $current[$j + 1] = max($current[$j], $prev[$j + 1]); + } + } + } + + return $current; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php new file mode 100644 index 0000000000..e55757c380 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/AbstractChunkOutputBuilder.php @@ -0,0 +1,52 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff\Output; + +use function count; + +abstract class AbstractChunkOutputBuilder implements DiffOutputBuilderInterface +{ + /** + * Takes input of the diff array and returns the common parts. + * Iterates through diff line by line. + */ + protected function getCommonChunks(array $diff, int $lineThreshold = 5): array + { + $diffSize = count($diff); + $capturing = false; + $chunkStart = 0; + $chunkSize = 0; + $commonChunks = []; + + for ($i = 0; $i < $diffSize; ++$i) { + if ($diff[$i][1] === 0 /* OLD */) { + if ($capturing === false) { + $capturing = true; + $chunkStart = $i; + $chunkSize = 0; + } else { + ++$chunkSize; + } + } elseif ($capturing !== false) { + if ($chunkSize >= $lineThreshold) { + $commonChunks[$chunkStart] = $chunkStart + $chunkSize; + } + + $capturing = false; + } + } + + if ($capturing !== false && $chunkSize >= $lineThreshold) { + $commonChunks[$chunkStart] = $chunkStart + $chunkSize; + } + + return $commonChunks; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php new file mode 100644 index 0000000000..f79a935cb8 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOnlyOutputBuilder.php @@ -0,0 +1,72 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff\Output; + +use function fclose; +use function fopen; +use function fwrite; +use function stream_get_contents; +use function substr; +use SebastianBergmann\Diff\Differ; + +/** + * Builds a diff string representation in a loose unified diff format + * listing only changes lines. Does not include line numbers. + */ +final class DiffOnlyOutputBuilder implements DiffOutputBuilderInterface +{ + /** + * @var string + */ + private $header; + + public function __construct(string $header = "--- Original\n+++ New\n") + { + $this->header = $header; + } + + public function getDiff(array $diff): string + { + $buffer = fopen('php://memory', 'r+b'); + + if ('' !== $this->header) { + fwrite($buffer, $this->header); + + if ("\n" !== substr($this->header, -1, 1)) { + fwrite($buffer, "\n"); + } + } + + foreach ($diff as $diffEntry) { + if ($diffEntry[1] === Differ::ADDED) { + fwrite($buffer, '+' . $diffEntry[0]); + } elseif ($diffEntry[1] === Differ::REMOVED) { + fwrite($buffer, '-' . $diffEntry[0]); + } elseif ($diffEntry[1] === Differ::DIFF_LINE_END_WARNING) { + fwrite($buffer, ' ' . $diffEntry[0]); + + continue; // Warnings should not be tested for line break, it will always be there + } else { /* Not changed (old) 0 */ + continue; // we didn't write the non changs line, so do not add a line break either + } + + $lc = substr($diffEntry[0], -1); + + if ($lc !== "\n" && $lc !== "\r") { + fwrite($buffer, "\n"); // \No newline at end of file + } + } + + $diff = stream_get_contents($buffer, -1, 0); + fclose($buffer); + + return $diff; + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOutputBuilderInterface.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOutputBuilderInterface.php new file mode 100644 index 0000000000..0e18f9f2e6 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/DiffOutputBuilderInterface.php @@ -0,0 +1,19 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff\Output; + +/** + * Defines how an output builder should take a generated + * diff array and return a string representation of that diff. + */ +interface DiffOutputBuilderInterface +{ + public function getDiff(array $diff): string; +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php new file mode 100644 index 0000000000..9c55ab2aaf --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/StrictUnifiedDiffOutputBuilder.php @@ -0,0 +1,338 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff\Output; + +use function array_merge; +use function array_splice; +use function count; +use function fclose; +use function fopen; +use function fwrite; +use function is_bool; +use function is_int; +use function is_string; +use function max; +use function min; +use function sprintf; +use function stream_get_contents; +use function substr; +use SebastianBergmann\Diff\ConfigurationException; +use SebastianBergmann\Diff\Differ; + +/** + * Strict Unified diff output builder. + * + * Generates (strict) Unified diff's (unidiffs) with hunks. + */ +final class StrictUnifiedDiffOutputBuilder implements DiffOutputBuilderInterface +{ + private static $default = [ + 'collapseRanges' => true, // ranges of length one are rendered with the trailing `,1` + 'commonLineThreshold' => 6, // number of same lines before ending a new hunk and creating a new one (if needed) + 'contextLines' => 3, // like `diff: -u, -U NUM, --unified[=NUM]`, for patch/git apply compatibility best to keep at least @ 3 + 'fromFile' => null, + 'fromFileDate' => null, + 'toFile' => null, + 'toFileDate' => null, + ]; + + /** + * @var bool + */ + private $changed; + + /** + * @var bool + */ + private $collapseRanges; + + /** + * @var int >= 0 + */ + private $commonLineThreshold; + + /** + * @var string + */ + private $header; + + /** + * @var int >= 0 + */ + private $contextLines; + + public function __construct(array $options = []) + { + $options = array_merge(self::$default, $options); + + if (!is_bool($options['collapseRanges'])) { + throw new ConfigurationException('collapseRanges', 'a bool', $options['collapseRanges']); + } + + if (!is_int($options['contextLines']) || $options['contextLines'] < 0) { + throw new ConfigurationException('contextLines', 'an int >= 0', $options['contextLines']); + } + + if (!is_int($options['commonLineThreshold']) || $options['commonLineThreshold'] <= 0) { + throw new ConfigurationException('commonLineThreshold', 'an int > 0', $options['commonLineThreshold']); + } + + $this->assertString($options, 'fromFile'); + $this->assertString($options, 'toFile'); + $this->assertStringOrNull($options, 'fromFileDate'); + $this->assertStringOrNull($options, 'toFileDate'); + + $this->header = sprintf( + "--- %s%s\n+++ %s%s\n", + $options['fromFile'], + null === $options['fromFileDate'] ? '' : "\t" . $options['fromFileDate'], + $options['toFile'], + null === $options['toFileDate'] ? '' : "\t" . $options['toFileDate'] + ); + + $this->collapseRanges = $options['collapseRanges']; + $this->commonLineThreshold = $options['commonLineThreshold']; + $this->contextLines = $options['contextLines']; + } + + public function getDiff(array $diff): string + { + if (0 === count($diff)) { + return ''; + } + + $this->changed = false; + + $buffer = fopen('php://memory', 'r+b'); + fwrite($buffer, $this->header); + + $this->writeDiffHunks($buffer, $diff); + + if (!$this->changed) { + fclose($buffer); + + return ''; + } + + $diff = stream_get_contents($buffer, -1, 0); + + fclose($buffer); + + // If the last char is not a linebreak: add it. + // This might happen when both the `from` and `to` do not have a trailing linebreak + $last = substr($diff, -1); + + return "\n" !== $last && "\r" !== $last + ? $diff . "\n" + : $diff; + } + + private function writeDiffHunks($output, array $diff): void + { + // detect "No newline at end of file" and insert into `$diff` if needed + + $upperLimit = count($diff); + + if (0 === $diff[$upperLimit - 1][1]) { + $lc = substr($diff[$upperLimit - 1][0], -1); + + if ("\n" !== $lc) { + array_splice($diff, $upperLimit, 0, [["\n\\ No newline at end of file\n", Differ::NO_LINE_END_EOF_WARNING]]); + } + } else { + // search back for the last `+` and `-` line, + // check if has trailing linebreak, else add under it warning under it + $toFind = [1 => true, 2 => true]; + + for ($i = $upperLimit - 1; $i >= 0; --$i) { + if (isset($toFind[$diff[$i][1]])) { + unset($toFind[$diff[$i][1]]); + $lc = substr($diff[$i][0], -1); + + if ("\n" !== $lc) { + array_splice($diff, $i + 1, 0, [["\n\\ No newline at end of file\n", Differ::NO_LINE_END_EOF_WARNING]]); + } + + if (!count($toFind)) { + break; + } + } + } + } + + // write hunks to output buffer + + $cutOff = max($this->commonLineThreshold, $this->contextLines); + $hunkCapture = false; + $sameCount = $toRange = $fromRange = 0; + $toStart = $fromStart = 1; + $i = 0; + + /** @var int $i */ + foreach ($diff as $i => $entry) { + if (0 === $entry[1]) { // same + if (false === $hunkCapture) { + ++$fromStart; + ++$toStart; + + continue; + } + + ++$sameCount; + ++$toRange; + ++$fromRange; + + if ($sameCount === $cutOff) { + $contextStartOffset = ($hunkCapture - $this->contextLines) < 0 + ? $hunkCapture + : $this->contextLines; + + // note: $contextEndOffset = $this->contextLines; + // + // because we never go beyond the end of the diff. + // with the cutoff/contextlines here the follow is never true; + // + // if ($i - $cutOff + $this->contextLines + 1 > \count($diff)) { + // $contextEndOffset = count($diff) - 1; + // } + // + // ; that would be true for a trailing incomplete hunk case which is dealt with after this loop + + $this->writeHunk( + $diff, + $hunkCapture - $contextStartOffset, + $i - $cutOff + $this->contextLines + 1, + $fromStart - $contextStartOffset, + $fromRange - $cutOff + $contextStartOffset + $this->contextLines, + $toStart - $contextStartOffset, + $toRange - $cutOff + $contextStartOffset + $this->contextLines, + $output + ); + + $fromStart += $fromRange; + $toStart += $toRange; + + $hunkCapture = false; + $sameCount = $toRange = $fromRange = 0; + } + + continue; + } + + $sameCount = 0; + + if ($entry[1] === Differ::NO_LINE_END_EOF_WARNING) { + continue; + } + + $this->changed = true; + + if (false === $hunkCapture) { + $hunkCapture = $i; + } + + if (Differ::ADDED === $entry[1]) { // added + ++$toRange; + } + + if (Differ::REMOVED === $entry[1]) { // removed + ++$fromRange; + } + } + + if (false === $hunkCapture) { + return; + } + + // we end here when cutoff (commonLineThreshold) was not reached, but we where capturing a hunk, + // do not render hunk till end automatically because the number of context lines might be less than the commonLineThreshold + + $contextStartOffset = $hunkCapture - $this->contextLines < 0 + ? $hunkCapture + : $this->contextLines; + + // prevent trying to write out more common lines than there are in the diff _and_ + // do not write more than configured through the context lines + $contextEndOffset = min($sameCount, $this->contextLines); + + $fromRange -= $sameCount; + $toRange -= $sameCount; + + $this->writeHunk( + $diff, + $hunkCapture - $contextStartOffset, + $i - $sameCount + $contextEndOffset + 1, + $fromStart - $contextStartOffset, + $fromRange + $contextStartOffset + $contextEndOffset, + $toStart - $contextStartOffset, + $toRange + $contextStartOffset + $contextEndOffset, + $output + ); + } + + private function writeHunk( + array $diff, + int $diffStartIndex, + int $diffEndIndex, + int $fromStart, + int $fromRange, + int $toStart, + int $toRange, + $output + ): void { + fwrite($output, '@@ -' . $fromStart); + + if (!$this->collapseRanges || 1 !== $fromRange) { + fwrite($output, ',' . $fromRange); + } + + fwrite($output, ' +' . $toStart); + + if (!$this->collapseRanges || 1 !== $toRange) { + fwrite($output, ',' . $toRange); + } + + fwrite($output, " @@\n"); + + for ($i = $diffStartIndex; $i < $diffEndIndex; ++$i) { + if ($diff[$i][1] === Differ::ADDED) { + $this->changed = true; + fwrite($output, '+' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::REMOVED) { + $this->changed = true; + fwrite($output, '-' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::OLD) { + fwrite($output, ' ' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::NO_LINE_END_EOF_WARNING) { + $this->changed = true; + fwrite($output, $diff[$i][0]); + } + //} elseif ($diff[$i][1] === Differ::DIFF_LINE_END_WARNING) { // custom comment inserted by PHPUnit/diff package + // skip + //} else { + // unknown/invalid + //} + } + } + + private function assertString(array $options, string $option): void + { + if (!is_string($options[$option])) { + throw new ConfigurationException($option, 'a string', $options[$option]); + } + } + + private function assertStringOrNull(array $options, string $option): void + { + if (null !== $options[$option] && !is_string($options[$option])) { + throw new ConfigurationException($option, 'a string or ', $options[$option]); + } + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php new file mode 100644 index 0000000000..8aae645043 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Output/UnifiedDiffOutputBuilder.php @@ -0,0 +1,272 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff\Output; + +use function array_splice; +use function count; +use function fclose; +use function fopen; +use function fwrite; +use function max; +use function min; +use function stream_get_contents; +use function strlen; +use function substr; +use SebastianBergmann\Diff\Differ; + +/** + * Builds a diff string representation in unified diff format in chunks. + */ +final class UnifiedDiffOutputBuilder extends AbstractChunkOutputBuilder +{ + /** + * @var bool + */ + private $collapseRanges = true; + + /** + * @var int >= 0 + */ + private $commonLineThreshold = 6; + + /** + * @var int >= 0 + */ + private $contextLines = 3; + + /** + * @var string + */ + private $header; + + /** + * @var bool + */ + private $addLineNumbers; + + public function __construct(string $header = "--- Original\n+++ New\n", bool $addLineNumbers = false) + { + $this->header = $header; + $this->addLineNumbers = $addLineNumbers; + } + + public function getDiff(array $diff): string + { + $buffer = fopen('php://memory', 'r+b'); + + if ('' !== $this->header) { + fwrite($buffer, $this->header); + + if ("\n" !== substr($this->header, -1, 1)) { + fwrite($buffer, "\n"); + } + } + + if (0 !== count($diff)) { + $this->writeDiffHunks($buffer, $diff); + } + + $diff = stream_get_contents($buffer, -1, 0); + + fclose($buffer); + + // If the diff is non-empty and last char is not a linebreak: add it. + // This might happen when both the `from` and `to` do not have a trailing linebreak + $last = substr($diff, -1); + + return 0 !== strlen($diff) && "\n" !== $last && "\r" !== $last + ? $diff . "\n" + : $diff; + } + + private function writeDiffHunks($output, array $diff): void + { + // detect "No newline at end of file" and insert into `$diff` if needed + + $upperLimit = count($diff); + + if (0 === $diff[$upperLimit - 1][1]) { + $lc = substr($diff[$upperLimit - 1][0], -1); + + if ("\n" !== $lc) { + array_splice($diff, $upperLimit, 0, [["\n\\ No newline at end of file\n", Differ::NO_LINE_END_EOF_WARNING]]); + } + } else { + // search back for the last `+` and `-` line, + // check if has trailing linebreak, else add under it warning under it + $toFind = [1 => true, 2 => true]; + + for ($i = $upperLimit - 1; $i >= 0; --$i) { + if (isset($toFind[$diff[$i][1]])) { + unset($toFind[$diff[$i][1]]); + $lc = substr($diff[$i][0], -1); + + if ("\n" !== $lc) { + array_splice($diff, $i + 1, 0, [["\n\\ No newline at end of file\n", Differ::NO_LINE_END_EOF_WARNING]]); + } + + if (!count($toFind)) { + break; + } + } + } + } + + // write hunks to output buffer + + $cutOff = max($this->commonLineThreshold, $this->contextLines); + $hunkCapture = false; + $sameCount = $toRange = $fromRange = 0; + $toStart = $fromStart = 1; + $i = 0; + + /** @var int $i */ + foreach ($diff as $i => $entry) { + if (0 === $entry[1]) { // same + if (false === $hunkCapture) { + ++$fromStart; + ++$toStart; + + continue; + } + + ++$sameCount; + ++$toRange; + ++$fromRange; + + if ($sameCount === $cutOff) { + $contextStartOffset = ($hunkCapture - $this->contextLines) < 0 + ? $hunkCapture + : $this->contextLines; + + // note: $contextEndOffset = $this->contextLines; + // + // because we never go beyond the end of the diff. + // with the cutoff/contextlines here the follow is never true; + // + // if ($i - $cutOff + $this->contextLines + 1 > \count($diff)) { + // $contextEndOffset = count($diff) - 1; + // } + // + // ; that would be true for a trailing incomplete hunk case which is dealt with after this loop + + $this->writeHunk( + $diff, + $hunkCapture - $contextStartOffset, + $i - $cutOff + $this->contextLines + 1, + $fromStart - $contextStartOffset, + $fromRange - $cutOff + $contextStartOffset + $this->contextLines, + $toStart - $contextStartOffset, + $toRange - $cutOff + $contextStartOffset + $this->contextLines, + $output + ); + + $fromStart += $fromRange; + $toStart += $toRange; + + $hunkCapture = false; + $sameCount = $toRange = $fromRange = 0; + } + + continue; + } + + $sameCount = 0; + + if ($entry[1] === Differ::NO_LINE_END_EOF_WARNING) { + continue; + } + + if (false === $hunkCapture) { + $hunkCapture = $i; + } + + if (Differ::ADDED === $entry[1]) { + ++$toRange; + } + + if (Differ::REMOVED === $entry[1]) { + ++$fromRange; + } + } + + if (false === $hunkCapture) { + return; + } + + // we end here when cutoff (commonLineThreshold) was not reached, but we where capturing a hunk, + // do not render hunk till end automatically because the number of context lines might be less than the commonLineThreshold + + $contextStartOffset = $hunkCapture - $this->contextLines < 0 + ? $hunkCapture + : $this->contextLines; + + // prevent trying to write out more common lines than there are in the diff _and_ + // do not write more than configured through the context lines + $contextEndOffset = min($sameCount, $this->contextLines); + + $fromRange -= $sameCount; + $toRange -= $sameCount; + + $this->writeHunk( + $diff, + $hunkCapture - $contextStartOffset, + $i - $sameCount + $contextEndOffset + 1, + $fromStart - $contextStartOffset, + $fromRange + $contextStartOffset + $contextEndOffset, + $toStart - $contextStartOffset, + $toRange + $contextStartOffset + $contextEndOffset, + $output + ); + } + + private function writeHunk( + array $diff, + int $diffStartIndex, + int $diffEndIndex, + int $fromStart, + int $fromRange, + int $toStart, + int $toRange, + $output + ): void { + if ($this->addLineNumbers) { + fwrite($output, '@@ -' . $fromStart); + + if (!$this->collapseRanges || 1 !== $fromRange) { + fwrite($output, ',' . $fromRange); + } + + fwrite($output, ' +' . $toStart); + + if (!$this->collapseRanges || 1 !== $toRange) { + fwrite($output, ',' . $toRange); + } + + fwrite($output, " @@\n"); + } else { + fwrite($output, "@@ @@\n"); + } + + for ($i = $diffStartIndex; $i < $diffEndIndex; ++$i) { + if ($diff[$i][1] === Differ::ADDED) { + fwrite($output, '+' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::REMOVED) { + fwrite($output, '-' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::OLD) { + fwrite($output, ' ' . $diff[$i][0]); + } elseif ($diff[$i][1] === Differ::NO_LINE_END_EOF_WARNING) { + fwrite($output, "\n"); // $diff[$i][0] + } else { /* Not changed (old) Differ::OLD or Warning Differ::DIFF_LINE_END_WARNING */ + fwrite($output, ' ' . $diff[$i][0]); + } + } + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Parser.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Parser.php new file mode 100644 index 0000000000..cc9e388712 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/Parser.php @@ -0,0 +1,110 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use function array_pop; +use function count; +use function max; +use function preg_match; +use function preg_split; + +/** + * Unified diff parser. + */ +final class Parser +{ + /** + * @return Diff[] + */ + public function parse(string $string): array + { + $lines = preg_split('(\r\n|\r|\n)', $string); + + if (!empty($lines) && $lines[count($lines) - 1] === '') { + array_pop($lines); + } + + $lineCount = count($lines); + $diffs = []; + $diff = null; + $collected = []; + + for ($i = 0; $i < $lineCount; ++$i) { + if (preg_match('#^---\h+"?(?P[^\\v\\t"]+)#', $lines[$i], $fromMatch) && + preg_match('#^\\+\\+\\+\\h+"?(?P[^\\v\\t"]+)#', $lines[$i + 1], $toMatch)) { + if ($diff !== null) { + $this->parseFileDiff($diff, $collected); + + $diffs[] = $diff; + $collected = []; + } + + $diff = new Diff($fromMatch['file'], $toMatch['file']); + + ++$i; + } else { + if (preg_match('/^(?:diff --git |index [\da-f\.]+|[+-]{3} [ab])/', $lines[$i])) { + continue; + } + + $collected[] = $lines[$i]; + } + } + + if ($diff !== null && count($collected)) { + $this->parseFileDiff($diff, $collected); + + $diffs[] = $diff; + } + + return $diffs; + } + + private function parseFileDiff(Diff $diff, array $lines): void + { + $chunks = []; + $chunk = null; + $diffLines = []; + + foreach ($lines as $line) { + if (preg_match('/^@@\s+-(?P\d+)(?:,\s*(?P\d+))?\s+\+(?P\d+)(?:,\s*(?P\d+))?\s+@@/', $line, $match)) { + $chunk = new Chunk( + (int) $match['start'], + isset($match['startrange']) ? max(1, (int) $match['startrange']) : 1, + (int) $match['end'], + isset($match['endrange']) ? max(1, (int) $match['endrange']) : 1 + ); + + $chunks[] = $chunk; + $diffLines = []; + + continue; + } + + if (preg_match('/^(?P[+ -])?(?P.*)/', $line, $match)) { + $type = Line::UNCHANGED; + + if ($match['type'] === '+') { + $type = Line::ADDED; + } elseif ($match['type'] === '-') { + $type = Line::REMOVED; + } + + $diffLines[] = new Line($type, $match['line']); + + if (null !== $chunk) { + $chunk->setLines($diffLines); + } + } + } + + $diff->setChunks($chunks); + } +} diff --git a/wcfsetup/install/files/lib/system/api/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php new file mode 100644 index 0000000000..fd19cac763 --- /dev/null +++ b/wcfsetup/install/files/lib/system/api/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php @@ -0,0 +1,70 @@ + + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace SebastianBergmann\Diff; + +use function array_reverse; +use function count; +use function max; +use SplFixedArray; + +final class TimeEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator +{ + /** + * {@inheritdoc} + */ + public function calculate(array $from, array $to): array + { + $common = []; + $fromLength = count($from); + $toLength = count($to); + $width = $fromLength + 1; + $matrix = new SplFixedArray($width * ($toLength + 1)); + + for ($i = 0; $i <= $fromLength; ++$i) { + $matrix[$i] = 0; + } + + for ($j = 0; $j <= $toLength; ++$j) { + $matrix[$j * $width] = 0; + } + + for ($i = 1; $i <= $fromLength; ++$i) { + for ($j = 1; $j <= $toLength; ++$j) { + $o = ($j * $width) + $i; + $matrix[$o] = max( + $matrix[$o - 1], + $matrix[$o - $width], + $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0 + ); + } + } + + $i = $fromLength; + $j = $toLength; + + while ($i > 0 && $j > 0) { + if ($from[$i - 1] === $to[$j - 1]) { + $common[] = $from[$i - 1]; + --$i; + --$j; + } else { + $o = ($j * $width) + $i; + + if ($matrix[$o - $width] > $matrix[$o - 1]) { + --$j; + } else { + --$i; + } + } + } + + return array_reverse($common); + } +} -- 2.20.1