From 18db984057b83ca4962c89b6b79bdce6a660b58f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 14:42:35 +0200 Subject: Adding upstream version 2.4.0. Signed-off-by: Daniel Baumann --- library/vendor/php-diff/README | 58 ++ library/vendor/php-diff/composer.json | 25 + library/vendor/php-diff/example/a.txt | 13 + library/vendor/php-diff/example/b.txt | 14 + library/vendor/php-diff/example/example.php | 69 ++ library/vendor/php-diff/example/styles.css | 93 +++ library/vendor/php-diff/lib/Diff.php | 177 +++++ .../vendor/php-diff/lib/Diff/Renderer/Abstract.php | 82 +++ .../php-diff/lib/Diff/Renderer/Html/Array.php | 233 +++++++ .../php-diff/lib/Diff/Renderer/Html/Inline.php | 143 ++++ .../php-diff/lib/Diff/Renderer/Html/SideBySide.php | 163 +++++ .../php-diff/lib/Diff/Renderer/Text/Context.php | 128 ++++ .../php-diff/lib/Diff/Renderer/Text/Unified.php | 87 +++ .../vendor/php-diff/lib/Diff/SequenceMatcher.php | 752 +++++++++++++++++++++ 14 files changed, 2037 insertions(+) create mode 100644 library/vendor/php-diff/README create mode 100644 library/vendor/php-diff/composer.json create mode 100644 library/vendor/php-diff/example/a.txt create mode 100644 library/vendor/php-diff/example/b.txt create mode 100644 library/vendor/php-diff/example/example.php create mode 100644 library/vendor/php-diff/example/styles.css create mode 100644 library/vendor/php-diff/lib/Diff.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Abstract.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Html/Array.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Html/Inline.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Html/SideBySide.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Text/Context.php create mode 100644 library/vendor/php-diff/lib/Diff/Renderer/Text/Unified.php create mode 100644 library/vendor/php-diff/lib/Diff/SequenceMatcher.php (limited to 'library/vendor/php-diff') diff --git a/library/vendor/php-diff/README b/library/vendor/php-diff/README new file mode 100644 index 0000000..f596115 --- /dev/null +++ b/library/vendor/php-diff/README @@ -0,0 +1,58 @@ +PHP Diff Class +-------------- + +Introduction +------------ +A comprehensive library for generating differences between +two hashable objects (strings or arrays). Generated differences can be +rendered in all of the standard formats including: + * Unified + * Context + * Inline HTML + * Side by Side HTML + +The logic behind the core of the diff engine (ie, the sequence matcher) +is primarily based on the Python difflib package. The reason for doing +so is primarily because of its high degree of accuracy. + +Example Use +----------- +A quick usage example can be found in the example/ directory and under +example.php. + +More complete documentation will be available shortly. + +Todo +---- + * Ability to ignore blank line changes + * 3 way diff support + * Performance optimizations + +License (BSD License) +--------------------- +Copyright (c) 2009 Chris Boulton +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 the Chris Boulton nor the names of its 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. \ No newline at end of file diff --git a/library/vendor/php-diff/composer.json b/library/vendor/php-diff/composer.json new file mode 100644 index 0000000..145c613 --- /dev/null +++ b/library/vendor/php-diff/composer.json @@ -0,0 +1,25 @@ +{ + "name": "phpspec/php-diff", + "type": "library", + "description": "A comprehensive library for generating differences between two hashable objects (strings or arrays).", + "license": "BSD-3-Clause", + + "authors": [ + { + "name": "Chris Boulton", + "homepage": "http://github.com/chrisboulton" + } + ], + + "autoload": { + "psr-0": { + "Diff": "lib/" + } + }, + + "extra": { + "branch-alias": { + "dev-master": "1.0.x-dev" + } + } +} diff --git a/library/vendor/php-diff/example/a.txt b/library/vendor/php-diff/example/a.txt new file mode 100644 index 0000000..6f3897b --- /dev/null +++ b/library/vendor/php-diff/example/a.txt @@ -0,0 +1,13 @@ + + + + Hello World! + + +

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

+ +

A heading we'll be removing

+ +

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

+ + \ No newline at end of file diff --git a/library/vendor/php-diff/example/b.txt b/library/vendor/php-diff/example/b.txt new file mode 100644 index 0000000..5918964 --- /dev/null +++ b/library/vendor/php-diff/example/b.txt @@ -0,0 +1,14 @@ + + + + Goodbye Cruel World! + + +

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

+ + +

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

+ +

Just a small amount of new text...

+ + \ No newline at end of file diff --git a/library/vendor/php-diff/example/example.php b/library/vendor/php-diff/example/example.php new file mode 100644 index 0000000..234bc2c --- /dev/null +++ b/library/vendor/php-diff/example/example.php @@ -0,0 +1,69 @@ + + + + + PHP LibDiff - Examples + + + +

PHP LibDiff - Examples

+
+ true, + //'ignoreCase' => true, + ); + + // Initialize the diff class + $diff = new Diff($a, $b, $options); + + ?> +

Side by Side Diff

+ Render($renderer); + + ?> +

Inline Diff

+ render($renderer); + + ?> +

Unified Diff

+ 
render($renderer));
+
+		?>
+
+

Context Diff

+ 
render($renderer));
+		?>
+
+ + \ No newline at end of file diff --git a/library/vendor/php-diff/example/styles.css b/library/vendor/php-diff/example/styles.css new file mode 100644 index 0000000..5454896 --- /dev/null +++ b/library/vendor/php-diff/example/styles.css @@ -0,0 +1,93 @@ +body { + background: #fff; + font-family: Arial; + font-size: 12px; +} +.Differences { + width: 100%; + border-collapse: collapse; + border-spacing: 0; + empty-cells: show; +} + +.Differences thead th { + text-align: left; + border-bottom: 1px solid #000; + background: #aaa; + color: #000; + padding: 4px; +} +.Differences tbody th { + text-align: right; + background: #ccc; + width: 4em; + padding: 1px 2px; + border-right: 1px solid #000; + vertical-align: top; + font-size: 13px; +} + +.Differences td { + padding: 1px 2px; + font-family: Consolas, monospace; + font-size: 13px; +} + +.DifferencesSideBySide .ChangeInsert td.Left { + background: #dfd; +} + +.DifferencesSideBySide .ChangeInsert td.Right { + background: #cfc; +} + +.DifferencesSideBySide .ChangeDelete td.Left { + background: #f88; +} + +.DifferencesSideBySide .ChangeDelete td.Right { + background: #faa; +} + +.DifferencesSideBySide .ChangeReplace .Left { + background: #fe9; +} + +.DifferencesSideBySide .ChangeReplace .Right { + background: #fd8; +} + +.Differences ins, .Differences del { + text-decoration: none; +} + +.DifferencesSideBySide .ChangeReplace ins, .DifferencesSideBySide .ChangeReplace del { + background: #fc0; +} + +.Differences .Skipped { + background: #f7f7f7; +} + +.DifferencesInline .ChangeReplace .Left, +.DifferencesInline .ChangeDelete .Left { + background: #fdd; +} + +.DifferencesInline .ChangeReplace .Right, +.DifferencesInline .ChangeInsert .Right { + background: #dfd; +} + +.DifferencesInline .ChangeReplace ins { + background: #9e9; +} + +.DifferencesInline .ChangeReplace del { + background: #e99; +} + +pre { + width: 100%; + overflow: auto; +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff.php b/library/vendor/php-diff/lib/Diff.php new file mode 100644 index 0000000..d6cecb7 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff.php @@ -0,0 +1,177 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package Diff + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +class Diff +{ + /** + * @var array The "old" sequence to use as the basis for the comparison. + */ + private $a = null; + + /** + * @var array The "new" sequence to generate the changes for. + */ + private $b = null; + + /** + * @var array Array containing the generated opcodes for the differences between the two items. + */ + private $groupedCodes = null; + + /** + * @var array Associative array of the default options available for the diff class and their default value. + */ + private $defaultOptions = array( + 'context' => 3, + 'ignoreNewLines' => false, + 'ignoreWhitespace' => false, + 'ignoreCase' => false + ); + + /** + * @var array Array of the options that have been applied for generating the diff. + */ + private $options = array(); + + /** + * The constructor. + * + * @param array $a Array containing the lines of the first string to compare. + * @param array $b Array containing the lines for the second string to compare. + * @param array $options + */ + public function __construct($a, $b, $options=array()) + { + $this->a = $a; + $this->b = $b; + + $this->options = array_merge($this->defaultOptions, $options); + } + + /** + * Render a diff using the supplied rendering class and return it. + * + * @param Diff_Renderer_Abstract $renderer An instance of the rendering object to use for generating the diff. + * @return mixed The generated diff. Exact return value depends on the rendered. + */ + public function render(Diff_Renderer_Abstract $renderer) + { + $renderer->diff = $this; + return $renderer->render(); + } + + /** + * Get a range of lines from $start to $end from the first comparison string + * and return them as an array. If no values are supplied, the entire string + * is returned. It's also possible to specify just one line to return only + * that line. + * + * @param int $start The starting number. + * @param int $end The ending number. If not supplied, only the item in $start will be returned. + * @return array Array of all of the lines between the specified range. + */ + public function getA($start=0, $end=null) + { + if($start == 0 && $end === null) { + return $this->a; + } + + if($end === null) { + $length = 1; + } + else { + $length = $end - $start; + } + + return array_slice($this->a, $start, $length); + + } + + /** + * Get a range of lines from $start to $end from the second comparison string + * and return them as an array. If no values are supplied, the entire string + * is returned. It's also possible to specify just one line to return only + * that line. + * + * @param int $start The starting number. + * @param int $end The ending number. If not supplied, only the item in $start will be returned. + * @return array Array of all of the lines between the specified range. + */ + public function getB($start=0, $end=null) + { + if($start == 0 && $end === null) { + return $this->b; + } + + if($end === null) { + $length = 1; + } + else { + $length = $end - $start; + } + + return array_slice($this->b, $start, $length); + } + + /** + * Generate a list of the compiled and grouped opcodes for the differences between the + * two strings. Generally called by the renderer, this class instantiates the sequence + * matcher and performs the actual diff generation and return an array of the opcodes + * for it. Once generated, the results are cached in the diff class instance. + * + * @return array Array of the grouped opcodes for the generated diff. + */ + public function getGroupedOpcodes() + { + if(!is_null($this->groupedCodes)) { + return $this->groupedCodes; + } + + require_once dirname(__FILE__).'/Diff/SequenceMatcher.php'; + $sequenceMatcher = new Diff_SequenceMatcher($this->a, $this->b, null, $this->options); + $this->groupedCodes = $sequenceMatcher->getGroupedOpcodes(); + return $this->groupedCodes; + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Abstract.php b/library/vendor/php-diff/lib/Diff/Renderer/Abstract.php new file mode 100644 index 0000000..f63c3e7 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Abstract.php @@ -0,0 +1,82 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +abstract class Diff_Renderer_Abstract +{ + /** + * @var object Instance of the diff class that this renderer is generating the rendered diff for. + */ + public $diff; + + /** + * @var array Array of the default options that apply to this renderer. + */ + protected $defaultOptions = array(); + + /** + * @var array Array containing the user applied and merged default options for the renderer. + */ + protected $options = array(); + + /** + * The constructor. Instantiates the rendering engine and if options are passed, + * sets the options for the renderer. + * + * @param array $options Optionally, an array of the options for the renderer. + */ + public function __construct(array $options = array()) + { + $this->setOptions($options); + } + + /** + * Set the options of the renderer to those supplied in the passed in array. + * Options are merged with the default to ensure that there aren't any missing + * options. + * + * @param array $options Array of options to set. + */ + public function setOptions(array $options) + { + $this->options = array_merge($this->defaultOptions, $options); + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Html/Array.php b/library/vendor/php-diff/lib/Diff/Renderer/Html/Array.php new file mode 100644 index 0000000..92bf128 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Html/Array.php @@ -0,0 +1,233 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +require_once dirname(__FILE__).'/../Abstract.php'; + +class Diff_Renderer_Html_Array extends Diff_Renderer_Abstract +{ + /** + * @var array Array of the default options that apply to this renderer. + */ + protected $defaultOptions = array( + 'tabSize' => 4 + ); + + /** + * Render and return an array structure suitable for generating HTML + * based differences. Generally called by subclasses that generate a + * HTML based diff and return an array of the changes to show in the diff. + * + * @return array An array of the generated chances, suitable for presentation in HTML. + */ + public function render() + { + // As we'll be modifying a & b to include our change markers, + // we need to get the contents and store them here. That way + // we're not going to destroy the original data + $a = $this->diff->getA(); + $b = $this->diff->getB(); + + $changes = array(); + $opCodes = $this->diff->getGroupedOpcodes(); + foreach($opCodes as $group) { + $blocks = array(); + $lastTag = null; + $lastBlock = 0; + foreach($group as $code) { + list($tag, $i1, $i2, $j1, $j2) = $code; + + if($tag == 'replace' && $i2 - $i1 == $j2 - $j1) { + for($i = 0; $i < ($i2 - $i1); ++$i) { + $fromLine = $a[$i1 + $i]; + $toLine = $b[$j1 + $i]; + + list($start, $end) = $this->getChangeExtent($fromLine, $toLine); + if($start != 0 || $end != 0) { + $realEnd = mb_strlen($fromLine) + $end; + $fromLine = mb_substr($fromLine, 0, $start) + . "\0" + . mb_substr($fromLine, $start, $realEnd - $start) + . "\1" + . mb_substr($fromLine, $realEnd); + $realEnd = mb_strlen($toLine) + $end; + $toLine = mb_substr($toLine, 0, $start) + . "\0" + . mb_substr($toLine, $start, $realEnd - $start) + . "\1" + . mb_substr($toLine, $realEnd); + $a[$i1 + $i] = $fromLine; + $b[$j1 + $i] = $toLine; + } + } + } + + if($tag != $lastTag) { + $blocks[] = array( + 'tag' => $tag, + 'base' => array( + 'offset' => $i1, + 'lines' => array() + ), + 'changed' => array( + 'offset' => $j1, + 'lines' => array() + ) + ); + $lastBlock = count($blocks)-1; + } + + $lastTag = $tag; + + if($tag == 'equal') { + $lines = array_slice($a, $i1, ($i2 - $i1)); + $blocks[$lastBlock]['base']['lines'] += $this->formatLines($lines); + $lines = array_slice($b, $j1, ($j2 - $j1)); + $blocks[$lastBlock]['changed']['lines'] += $this->formatLines($lines); + } + else { + if($tag == 'replace' || $tag == 'delete') { + $lines = array_slice($a, $i1, ($i2 - $i1)); + $lines = $this->formatLines($lines); + $lines = str_replace(array("\0", "\1"), array('', ''), $lines); + $blocks[$lastBlock]['base']['lines'] += $lines; + } + + if($tag == 'replace' || $tag == 'insert') { + $lines = array_slice($b, $j1, ($j2 - $j1)); + $lines = $this->formatLines($lines); + $lines = str_replace(array("\0", "\1"), array('', ''), $lines); + $blocks[$lastBlock]['changed']['lines'] += $lines; + } + } + } + $changes[] = $blocks; + } + return $changes; + } + + /** + * Given two strings, determine where the changes in the two strings + * begin, and where the changes in the two strings end. + * + * @param string $fromLine The first string. + * @param string $toLine The second string. + * @return array Array containing the starting position (0 by default) and the ending position (-1 by default) + */ + private function getChangeExtent($fromLine, $toLine) + { + $start = 0; + $limit = min(mb_strlen($fromLine), mb_strlen($toLine)); + while($start < $limit && mb_substr($fromLine, $start, 1) == mb_substr($toLine, $start, 1)) { + ++$start; + } + $end = -1; + $limit = $limit - $start; + while(-$end <= $limit && mb_substr($fromLine, $end, 1) == mb_substr($toLine, $end, 1)) { + --$end; + } + return array( + $start, + $end + 1 + ); + } + + /** + * Format a series of lines suitable for output in a HTML rendered diff. + * This involves replacing tab characters with spaces, making the HTML safe + * for output, ensuring that double spaces are replaced with   etc. + * + * @param array $lines Array of lines to format. + * @return array Array of the formatted lines. + */ + private function formatLines($lines) + { + if ($this->options['tabSize'] !== false) { + $lines = array_map(array($this, 'ExpandTabs'), $lines); + } + $lines = array_map(array($this, 'HtmlSafe'), $lines); + foreach($lines as &$line) { + $line = preg_replace_callback('# ( +)|^ #', __CLASS__."::fixSpaces", $line); + } + return $lines; + } + + /** + * Replace a string containing spaces with a HTML representation using  . + * + * @param string $matches Regex matches array. + * @return string The HTML representation of the string. + */ + public static function fixSpaces($matches) + { + $spaces = isset($matches[1]) ? $matches[1] : ''; + $count = strlen($spaces); + if($count == 0) { + return ''; + } + + $div = floor($count / 2); + $mod = $count % 2; + return str_repeat('  ', $div).str_repeat(' ', $mod); + } + + /** + * Replace tabs in a single line with a number of spaces as defined by the tabSize option. + * + * @param string $line The containing tabs to convert. + * @return string The line with the tabs converted to spaces. + */ + private function expandTabs($line) + { + return str_replace("\t", str_repeat(' ', $this->options['tabSize']), $line); + } + + /** + * Make a string containing HTML safe for output on a page. + * + * @param string $string The string. + * @return string The string with the HTML characters replaced by entities. + */ + private function htmlSafe($string) + { + return htmlspecialchars($string, ENT_NOQUOTES, 'UTF-8'); + } +} diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Html/Inline.php b/library/vendor/php-diff/lib/Diff/Renderer/Html/Inline.php new file mode 100644 index 0000000..70cc904 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Html/Inline.php @@ -0,0 +1,143 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +require_once dirname(__FILE__).'/Array.php'; + +class Diff_Renderer_Html_Inline extends Diff_Renderer_Html_Array +{ + /** + * Render a and return diff with changes between the two sequences + * displayed inline (under each other) + * + * @return string The generated inline diff. + */ + public function render() + { + $changes = parent::render(); + $html = ''; + if(empty($changes)) { + return $html; + } + + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + foreach($changes as $i => $blocks) { + // If this is a separate block, we're condensing code so output ..., + // indicating a significant portion of the code has been collapsed as + // it is the same + if($i > 0) { + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + + foreach($blocks as $change) { + $html .= ''; + // Equal changes should be shown on both sides of the diff + if($change['tag'] == 'equal') { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Added lines only on the right side + else if($change['tag'] == 'insert') { + foreach($change['changed']['lines'] as $no => $line) { + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Show deleted lines only on the left side + else if($change['tag'] == 'delete') { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Show modified lines on both sides + else if($change['tag'] == 'replace') { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + + foreach($change['changed']['lines'] as $no => $line) { + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + $html .= ''; + } + } + $html .= '
OldNewDifferences
…… 
'.$fromLine.''.$toLine.''.$line.'
 '.$toLine.''.$line.' 
'.$fromLine.' '.$line.' 
'.$fromLine.' '.$line.'
 '.$toLine.''.$line.'
'; + return $html; + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Html/SideBySide.php b/library/vendor/php-diff/lib/Diff/Renderer/Html/SideBySide.php new file mode 100644 index 0000000..eb43848 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Html/SideBySide.php @@ -0,0 +1,163 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +require_once dirname(__FILE__).'/Array.php'; + +class Diff_Renderer_Html_SideBySide extends Diff_Renderer_Html_Array +{ + /** + * Render a and return diff with changes between the two sequences + * displayed side by side. + * + * @return string The generated side by side diff. + */ + public function render() + { + $changes = parent::render(); + + $html = ''; + if(empty($changes)) { + return $html; + } + + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + foreach($changes as $i => $blocks) { + if($i > 0) { + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + + foreach($blocks as $change) { + $html .= ''; + // Equal changes should be shown on both sides of the diff + if($change['tag'] == 'equal') { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Added lines only on the right side + else if($change['tag'] == 'insert') { + foreach($change['changed']['lines'] as $no => $line) { + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Show deleted lines only on the left side + else if($change['tag'] == 'delete') { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + // Show modified lines on both sides + else if($change['tag'] == 'replace') { + if(count($change['base']['lines']) >= count($change['changed']['lines'])) { + foreach($change['base']['lines'] as $no => $line) { + $fromLine = $change['base']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + if(!isset($change['changed']['lines'][$no])) { + $toLine = ' '; + $changedLine = ' '; + } + else { + $toLine = $change['base']['offset'] + $no + 1; + $changedLine = ''.$change['changed']['lines'][$no].''; + } + $html .= ''; + $html .= ''; + $html .= ''; + } + } + else { + foreach($change['changed']['lines'] as $no => $changedLine) { + if(!isset($change['base']['lines'][$no])) { + $fromLine = ' '; + $line = ' '; + } + else { + $fromLine = $change['base']['offset'] + $no + 1; + $line = ''.$change['base']['lines'][$no].''; + } + $html .= ''; + $html .= ''; + $html .= ''; + $toLine = $change['changed']['offset'] + $no + 1; + $html .= ''; + $html .= ''; + $html .= ''; + } + } + } + $html .= ''; + } + } + $html .= '
Old VersionNew Version
… … 
'.$fromLine.''.$line.' '.$toLine.''.$line.' 
  '.$toLine.''.$line.' 
'.$fromLine.''.$line.'   
'.$fromLine.''.$line.' '.$toLine.''.$changedLine.'
'.$fromLine.''.$line.' '.$toLine.''.$changedLine.'
'; + return $html; + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Text/Context.php b/library/vendor/php-diff/lib/Diff/Renderer/Text/Context.php new file mode 100644 index 0000000..241b965 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Text/Context.php @@ -0,0 +1,128 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +require_once dirname(__FILE__).'/../Abstract.php'; + +class Diff_Renderer_Text_Context extends Diff_Renderer_Abstract +{ + /** + * @var array Array of the different opcode tags and how they map to the context diff equivalent. + */ + private $tagMap = array( + 'insert' => '+', + 'delete' => '-', + 'replace' => '!', + 'equal' => ' ' + ); + + /** + * Render and return a context formatted (old school!) diff file. + * + * @return string The generated context diff. + */ + public function render() + { + $diff = ''; + $opCodes = $this->diff->getGroupedOpcodes(); + foreach($opCodes as $group) { + $diff .= "***************\n"; + $lastItem = count($group)-1; + $i1 = $group[0][1]; + $i2 = $group[$lastItem][2]; + $j1 = $group[0][3]; + $j2 = $group[$lastItem][4]; + + if($i2 - $i1 >= 2) { + $diff .= '*** '.($group[0][1] + 1).','.$i2." ****".PHP_EOL; + } + else { + $diff .= '*** '.$i2." ****\n"; + } + + if($j2 - $j1 >= 2) { + $separator = '--- '.($j1 + 1).','.$j2." ----".PHP_EOL; + } + else { + $separator = '--- '.$j2." ----".PHP_EOL; + } + + $hasVisible = false; + foreach($group as $code) { + if($code[0] == 'replace' || $code[0] == 'delete') { + $hasVisible = true; + break; + } + } + + if($hasVisible) { + foreach($group as $code) { + list($tag, $i1, $i2, $j1, $j2) = $code; + if($tag == 'insert') { + continue; + } + $diff .= $this->tagMap[$tag].' '.implode(PHP_EOL.$this->tagMap[$tag].' ', $this->diff->GetA($i1, $i2)).PHP_EOL; + } + } + + $hasVisible = false; + foreach($group as $code) { + if($code[0] == 'replace' || $code[0] == 'insert') { + $hasVisible = true; + break; + } + } + + $diff .= $separator; + + if($hasVisible) { + foreach($group as $code) { + list($tag, $i1, $i2, $j1, $j2) = $code; + if($tag == 'delete') { + continue; + } + $diff .= $this->tagMap[$tag].' '.implode(PHP_EOL.$this->tagMap[$tag].' ', $this->diff->GetB($j1, $j2)).PHP_EOL; + } + } + } + return $diff; + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/Renderer/Text/Unified.php b/library/vendor/php-diff/lib/Diff/Renderer/Text/Unified.php new file mode 100644 index 0000000..084611c --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/Renderer/Text/Unified.php @@ -0,0 +1,87 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package DiffLib + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +require_once dirname(__FILE__).'/../Abstract.php'; + +class Diff_Renderer_Text_Unified extends Diff_Renderer_Abstract +{ + /** + * Render and return a unified diff. + * + * @return string The unified diff. + */ + public function render() + { + $diff = ''; + $opCodes = $this->diff->getGroupedOpcodes(); + foreach($opCodes as $group) { + $lastItem = count($group)-1; + $i1 = $group[0][1]; + $i2 = $group[$lastItem][2]; + $j1 = $group[0][3]; + $j2 = $group[$lastItem][4]; + + if($i1 == 0 && $i2 == 0) { + $i1 = -1; + $i2 = -1; + } + + $diff .= '@@ -'.($i1 + 1).','.($i2 - $i1).' +'.($j1 + 1).','.($j2 - $j1)." @@".PHP_EOL; + foreach($group as $code) { + list($tag, $i1, $i2, $j1, $j2) = $code; + if($tag == 'equal') { + $diff .= ' '.implode(PHP_EOL." ", $this->diff->GetA($i1, $i2)).PHP_EOL; + } + else { + if($tag == 'replace' || $tag == 'delete') { + $diff .= '-'.implode(PHP_EOL."-", $this->diff->GetA($i1, $i2)).PHP_EOL; + } + + if($tag == 'replace' || $tag == 'insert') { + $diff .= '+'.implode(PHP_EOL."+", $this->diff->GetB($j1, $j2)).PHP_EOL; + } + } + } + } + return $diff; + } +} \ No newline at end of file diff --git a/library/vendor/php-diff/lib/Diff/SequenceMatcher.php b/library/vendor/php-diff/lib/Diff/SequenceMatcher.php new file mode 100644 index 0000000..71c9c63 --- /dev/null +++ b/library/vendor/php-diff/lib/Diff/SequenceMatcher.php @@ -0,0 +1,752 @@ + + * + * 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 the Chris Boulton nor the names of its 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. + * + * @package Diff + * @author Chris Boulton + * @copyright (c) 2009 Chris Boulton + * @license New BSD License http://www.opensource.org/licenses/bsd-license.php + * @version 1.1 + * @link http://github.com/chrisboulton/php-diff + */ + +class Diff_SequenceMatcher +{ + /** + * @var string|array Either a string or an array containing a callback function to determine if a line is "junk" or not. + */ + private $junkCallback = null; + + /** + * @var array The first sequence to compare against. + */ + private $a = null; + + /** + * @var array The second sequence. + */ + private $b = null; + + /** + * @var array Array of characters that are considered junk from the second sequence. Characters are the array key. + */ + private $junkDict = array(); + + /** + * @var array Array of indices that do not contain junk elements. + */ + private $b2j = array(); + + private $options = array(); + + private $matchingBlocks = null; + private $opCodes = null; + private $fullBCount = null; + + private $defaultOptions = array( + 'ignoreNewLines' => false, + 'ignoreWhitespace' => false, + 'ignoreCase' => false + ); + + /** + * The constructor. With the sequences being passed, they'll be set for the + * sequence matcher and it will perform a basic cleanup & calculate junk + * elements. + * + * @param string|array $a A string or array containing the lines to compare against. + * @param string|array $b A string or array containing the lines to compare. + * @param string|array $junkCallback Either an array or string that references a callback function (if there is one) to determine 'junk' characters. + * @param array $options + */ + public function __construct($a, $b, $junkCallback=null, $options=[]) + { + $this->a = null; + $this->b = null; + $this->junkCallback = $junkCallback; + $this->setOptions($options); + $this->setSequences($a, $b); + } + + /** + * Set new options + * + * @param array $options + */ + public function setOptions($options) + { + $this->options = array_merge($this->defaultOptions, $options); + } + + /** + * Set the first and second sequences to use with the sequence matcher. + * + * @param string|array $a A string or array containing the lines to compare against. + * @param string|array $b A string or array containing the lines to compare. + */ + public function setSequences($a, $b) + { + $this->setSeq1($a); + $this->setSeq2($b); + } + + /** + * Set the first sequence ($a) and reset any internal caches to indicate that + * when calling the calculation methods, we need to recalculate them. + * + * @param string|array $a The sequence to set as the first sequence. + */ + public function setSeq1($a) + { + if(!is_array($a)) { + $a = str_split($a); + } + if($a == $this->a) { + return; + } + + $this->a= $a; + $this->matchingBlocks = null; + $this->opCodes = null; + } + + /** + * Set the second sequence ($b) and reset any internal caches to indicate that + * when calling the calculation methods, we need to recalculate them. + * + * @param string|array $b The sequence to set as the second sequence. + */ + public function setSeq2($b) + { + if(!is_array($b)) { + $b = str_split($b); + } + if($b == $this->b) { + return; + } + + $this->b = $b; + $this->matchingBlocks = null; + $this->opCodes = null; + $this->fullBCount = null; + $this->chainB(); + } + + /** + * Generate the internal arrays containing the list of junk and non-junk + * characters for the second ($b) sequence. + */ + private function chainB() + { + $length = count ($this->b); + $this->b2j = array(); + $popularDict = array(); + + for($i = 0; $i < $length; ++$i) { + $char = $this->b[$i]; + if(isset($this->b2j[$char])) { + if($length >= 200 && count($this->b2j[$char]) * 100 > $length) { + $popularDict[$char] = 1; + unset($this->b2j[$char]); + } + else { + $this->b2j[$char][] = $i; + } + } + else { + $this->b2j[$char] = array( + $i + ); + } + } + + // Remove leftovers + foreach(array_keys($popularDict) as $char) { + unset($this->b2j[$char]); + } + + $this->junkDict = array(); + if(is_callable($this->junkCallback)) { + foreach(array_keys($popularDict) as $char) { + if(call_user_func($this->junkCallback, $char)) { + $this->junkDict[$char] = 1; + unset($popularDict[$char]); + } + } + + foreach(array_keys($this->b2j) as $char) { + if(call_user_func($this->junkCallback, $char)) { + $this->junkDict[$char] = 1; + unset($this->b2j[$char]); + } + } + } + } + + /** + * Checks if a particular character is in the junk dictionary + * for the list of junk characters. + * @param $b + * @return boolean True if the character is considered junk. False if not. + */ + private function isBJunk($b) + { + if(isset($this->junkDict[$b])) { + return true; + } + + return false; + } + + /** + * Find the longest matching block in the two sequences, as defined by the + * lower and upper constraints for each sequence. (for the first sequence, + * $alo - $ahi and for the second sequence, $blo - $bhi) + * + * Essentially, of all of the maximal matching blocks, return the one that + * startest earliest in $a, and all of those maximal matching blocks that + * start earliest in $a, return the one that starts earliest in $b. + * + * If the junk callback is defined, do the above but with the restriction + * that the junk element appears in the block. Extend it as far as possible + * by matching only junk elements in both $a and $b. + * + * @param int $alo The lower constraint for the first sequence. + * @param int $ahi The upper constraint for the first sequence. + * @param int $blo The lower constraint for the second sequence. + * @param int $bhi The upper constraint for the second sequence. + * @return array Array containing the longest match that includes the starting position in $a, start in $b and the length/size. + */ + public function findLongestMatch($alo, $ahi, $blo, $bhi) + { + $a = $this->a; + $b = $this->b; + + $bestI = $alo; + $bestJ = $blo; + $bestSize = 0; + + $j2Len = array(); + $nothing = array(); + + for($i = $alo; $i < $ahi; ++$i) { + $newJ2Len = array(); + $jDict = $this->arrayGetDefault($this->b2j, $a[$i], $nothing); + foreach($jDict as $j) { + if($j < $blo) { + continue; + } + else if($j >= $bhi) { + break; + } + + $k = $this->arrayGetDefault($j2Len, $j -1, 0) + 1; + $newJ2Len[$j] = $k; + if($k > $bestSize) { + $bestI = $i - $k + 1; + $bestJ = $j - $k + 1; + $bestSize = $k; + } + } + + $j2Len = $newJ2Len; + } + + while($bestI > $alo && $bestJ > $blo && !$this->isBJunk($b[$bestJ - 1]) && + !$this->linesAreDifferent($bestI - 1, $bestJ - 1)) { + --$bestI; + --$bestJ; + ++$bestSize; + } + + while($bestI + $bestSize < $ahi && ($bestJ + $bestSize) < $bhi && + !$this->isBJunk($b[$bestJ + $bestSize]) && !$this->linesAreDifferent($bestI + $bestSize, $bestJ + $bestSize)) { + ++$bestSize; + } + + while($bestI > $alo && $bestJ > $blo && $this->isBJunk($b[$bestJ - 1]) && + !$this->linesAreDifferent($bestI - 1, $bestJ - 1)) { + --$bestI; + --$bestJ; + ++$bestSize; + } + + while($bestI + $bestSize < $ahi && $bestJ + $bestSize < $bhi && + $this->isBJunk($b[$bestJ + $bestSize]) && !$this->linesAreDifferent($bestI + $bestSize, $bestJ + $bestSize)) { + ++$bestSize; + } + + return array( + $bestI, + $bestJ, + $bestSize + ); + } + + /** + * Check if the two lines at the given indexes are different or not. + * + * @param int $aIndex Line number to check against in a. + * @param int $bIndex Line number to check against in b. + * @return boolean True if the lines are different and false if not. + */ + public function linesAreDifferent($aIndex, $bIndex) + { + $lineA = $this->a[$aIndex]; + $lineB = $this->b[$bIndex]; + + if($this->options['ignoreWhitespace']) { + $replace = array("\t", ' '); + $lineA = str_replace($replace, '', $lineA); + $lineB = str_replace($replace, '', $lineB); + } + + if($this->options['ignoreCase']) { + $lineA = strtolower($lineA); + $lineB = strtolower($lineB); + } + + if($lineA != $lineB) { + return true; + } + + return false; + } + + /** + * Return a nested set of arrays for all of the matching sub-sequences + * in the strings $a and $b. + * + * Each block contains the lower constraint of the block in $a, the lower + * constraint of the block in $b and finally the number of lines that the + * block continues for. + * + * @return array Nested array of the matching blocks, as described by the function. + */ + public function getMatchingBlocks() + { + if(!empty($this->matchingBlocks)) { + return $this->matchingBlocks; + } + + $aLength = count($this->a); + $bLength = count($this->b); + + $queue = array( + array( + 0, + $aLength, + 0, + $bLength + ) + ); + + $matchingBlocks = array(); + while(!empty($queue)) { + list($alo, $ahi, $blo, $bhi) = array_pop($queue); + $x = $this->findLongestMatch($alo, $ahi, $blo, $bhi); + list($i, $j, $k) = $x; + if($k) { + $matchingBlocks[] = $x; + if($alo < $i && $blo < $j) { + $queue[] = array( + $alo, + $i, + $blo, + $j + ); + } + + if($i + $k < $ahi && $j + $k < $bhi) { + $queue[] = array( + $i + $k, + $ahi, + $j + $k, + $bhi + ); + } + } + } + + usort($matchingBlocks, array($this, 'tupleSort')); + + $i1 = 0; + $j1 = 0; + $k1 = 0; + $nonAdjacent = array(); + foreach($matchingBlocks as $block) { + list($i2, $j2, $k2) = $block; + if($i1 + $k1 == $i2 && $j1 + $k1 == $j2) { + $k1 += $k2; + } + else { + if($k1) { + $nonAdjacent[] = array( + $i1, + $j1, + $k1 + ); + } + + $i1 = $i2; + $j1 = $j2; + $k1 = $k2; + } + } + + if($k1) { + $nonAdjacent[] = array( + $i1, + $j1, + $k1 + ); + } + + $nonAdjacent[] = array( + $aLength, + $bLength, + 0 + ); + + $this->matchingBlocks = $nonAdjacent; + return $this->matchingBlocks; + } + + /** + * Return a list of all of the opcodes for the differences between the + * two strings. + * + * The nested array returned contains an array describing the opcode + * which includes: + * 0 - The type of tag (as described below) for the opcode. + * 1 - The beginning line in the first sequence. + * 2 - The end line in the first sequence. + * 3 - The beginning line in the second sequence. + * 4 - The end line in the second sequence. + * + * The different types of tags include: + * replace - The string from $i1 to $i2 in $a should be replaced by + * the string in $b from $j1 to $j2. + * delete - The string in $a from $i1 to $j2 should be deleted. + * insert - The string in $b from $j1 to $j2 should be inserted at + * $i1 in $a. + * equal - The two strings with the specified ranges are equal. + * + * @return array Array of the opcodes describing the differences between the strings. + */ + public function getOpCodes() + { + if(!empty($this->opCodes)) { + return $this->opCodes; + } + + $i = 0; + $j = 0; + $this->opCodes = array(); + + $blocks = $this->getMatchingBlocks(); + foreach($blocks as $block) { + list($ai, $bj, $size) = $block; + $tag = ''; + if($i < $ai && $j < $bj) { + $tag = 'replace'; + } + else if($i < $ai) { + $tag = 'delete'; + } + else if($j < $bj) { + $tag = 'insert'; + } + + if($tag) { + $this->opCodes[] = array( + $tag, + $i, + $ai, + $j, + $bj + ); + } + + $i = $ai + $size; + $j = $bj + $size; + + if($size) { + $this->opCodes[] = array( + 'equal', + $ai, + $i, + $bj, + $j + ); + } + } + return $this->opCodes; + } + + /** + * Return a series of nested arrays containing different groups of generated + * opcodes for the differences between the strings with up to $context lines + * of surrounding content. + * + * Essentially what happens here is any big equal blocks of strings are stripped + * out, the smaller subsets of changes are then arranged in to their groups. + * This means that the sequence matcher and diffs do not need to include the full + * content of the different files but can still provide context as to where the + * changes are. + * + * @param int $context The number of lines of context to provide around the groups. + * @return array Nested array of all of the grouped opcodes. + */ + public function getGroupedOpcodes($context=3) + { + $opCodes = $this->getOpCodes(); + if(empty($opCodes)) { + $opCodes = array( + array( + 'equal', + 0, + 1, + 0, + 1 + ) + ); + } + + if($opCodes[0][0] == 'equal') { + $opCodes[0] = array( + $opCodes[0][0], + max($opCodes[0][1], $opCodes[0][2] - $context), + $opCodes[0][2], + max($opCodes[0][3], $opCodes[0][4] - $context), + $opCodes[0][4] + ); + } + + $lastItem = count($opCodes) - 1; + if($opCodes[$lastItem][0] == 'equal') { + list($tag, $i1, $i2, $j1, $j2) = $opCodes[$lastItem]; + $opCodes[$lastItem] = array( + $tag, + $i1, + min($i2, $i1 + $context), + $j1, + min($j2, $j1 + $context) + ); + } + + $maxRange = $context * 2; + $groups = array(); + $group = array(); + foreach($opCodes as $code) { + list($tag, $i1, $i2, $j1, $j2) = $code; + if($tag == 'equal' && $i2 - $i1 > $maxRange) { + $group[] = array( + $tag, + $i1, + min($i2, $i1 + $context), + $j1, + min($j2, $j1 + $context) + ); + $groups[] = $group; + $group = array(); + $i1 = max($i1, $i2 - $context); + $j1 = max($j1, $j2 - $context); + } + $group[] = array( + $tag, + $i1, + $i2, + $j1, + $j2 + ); + } + + if(!empty($group) && !(count($group) == 1 && $group[0][0] == 'equal')) { + $groups[] = $group; + } + + return $groups; + } + + /** + * Return a measure of the similarity between the two sequences. + * This will be a float value between 0 and 1. + * + * Out of all of the ratio calculation functions, this is the most + * expensive to call if getMatchingBlocks or getOpCodes is yet to be + * called. The other calculation methods (quickRatio and realquickRatio) + * can be used to perform quicker calculations but may be less accurate. + * + * The ratio is calculated as (2 * number of matches) / total number of + * elements in both sequences. + * + * @return float The calculated ratio. + */ + public function Ratio() + { + $matches = array_reduce($this->getMatchingBlocks(), array($this, 'ratioReduce'), 0); + return $this->calculateRatio($matches, count ($this->a) + count ($this->b)); + } + + /** + * Helper function to calculate the number of matches for Ratio(). + * + * @param int $sum The running total for the number of matches. + * @param array $triple Array containing the matching block triple to add to the running total. + * @return int The new running total for the number of matches. + */ + private function ratioReduce($sum, $triple) + { + return $sum + ($triple[count($triple) - 1]); + } + + /** + * Quickly return an upper bound ratio for the similarity of the strings. + * This is quicker to compute than Ratio(). + * + * @return float The calculated ratio. + */ + private function quickRatio() + { + if($this->fullBCount === null) { + $this->fullBCount = array(); + $bLength = count ($this->b); + for($i = 0; $i < $bLength; ++$i) { + $char = $this->b[$i]; + $this->fullBCount[$char] = $this->arrayGetDefault($this->fullBCount, $char, 0) + 1; + } + } + + $avail = array(); + $matches = 0; + $aLength = count ($this->a); + for($i = 0; $i < $aLength; ++$i) { + $char = $this->a[$i]; + if(isset($avail[$char])) { + $numb = $avail[$char]; + } + else { + $numb = $this->arrayGetDefault($this->fullBCount, $char, 0); + } + $avail[$char] = $numb - 1; + if($numb > 0) { + ++$matches; + } + } + + $this->calculateRatio($matches, count ($this->a) + count ($this->b)); + } + + /** + * Return an upper bound ratio really quickly for the similarity of the strings. + * This is quicker to compute than Ratio() and quickRatio(). + * + * @return float The calculated ratio. + */ + private function realquickRatio() + { + $aLength = count ($this->a); + $bLength = count ($this->b); + + return $this->calculateRatio(min($aLength, $bLength), $aLength + $bLength); + } + + /** + * Helper function for calculating the ratio to measure similarity for the strings. + * The ratio is defined as being 2 * (number of matches / total length) + * + * @param int $matches The number of matches in the two strings. + * @param int $length The length of the two strings. + * @return float The calculated ratio. + */ + private function calculateRatio($matches, $length=0) + { + if($length) { + return 2 * ($matches / $length); + } + else { + return 1; + } + } + + /** + * Helper function that provides the ability to return the value for a key + * in an array of it exists, or if it doesn't then return a default value. + * Essentially cleaner than doing a series of if(isset()) {} else {} calls. + * + * @param array $array The array to search. + * @param string $key The key to check that exists. + * @param mixed $default The value to return as the default value if the key doesn't exist. + * @return mixed The value from the array if the key exists or otherwise the default. + */ + private function arrayGetDefault($array, $key, $default) + { + if(isset($array[$key])) { + return $array[$key]; + } + else { + return $default; + } + } + + /** + * Sort an array by the nested arrays it contains. Helper function for getMatchingBlocks + * + * @param array $a First array to compare. + * @param array $b Second array to compare. + * @return int -1, 0 or 1, as expected by the usort function. + */ + private function tupleSort($a, $b) + { + $max = max(count($a), count($b)); + for($i = 0; $i < $max; ++$i) { + if($a[$i] < $b[$i]) { + return -1; + } + else if($a[$i] > $b[$i]) { + return 1; + } + } + + if(count($a) == count($b)) { + return 0; + } + else if(count($a) < count($b)) { + return -1; + } + else { + return 1; + } + } +} -- cgit v1.2.3