includes/diff/DairikiDiff.php

   1 <?php
   2 /**
   3  * A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
   4  *
   5  * Copyright © 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
   6  * You may copy this code freely under the conditions of the GPL.
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; if not, write to the Free Software Foundation, Inc.,
  20  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21  * http://www.gnu.org/copyleft/gpl.html
  22  *
  23  * @file
  24  * @ingroup DifferenceEngine
  25  * @defgroup DifferenceEngine DifferenceEngine
  26  */
  27
  28 /**
  29  * The base class for all other DiffOp classes.
  30  *
  31  * The classes that extend DiffOp are: DiffOpCopy, DiffOpDelete, DiffOpAdd and
  32  * DiffOpChange. FakeDiffOp also extends DiffOp, but it is not located in this file.
  33  *
  34  * @private
  35  * @ingroup DifferenceEngine
  36  */
  37 abstract class DiffOp {
  38
  39         /**
  40          * @var string
  41          */
  42         public $type;
  43
  44         /**
  45          * @var string[]
  46          */
  47         public $orig;
  48
  49         /**
  50          * @var string[]
  51          */
  52         public $closing;
  53
  54         /**
  55          * @return string
  56          */
  57         public function getType() {
  58                 return $this->type;
  59         }
  60
  61         /**
  62          * @return string[]
  63          */
  64         public function getOrig() {
  65                 return $this->orig;
  66         }
  67
  68         /**
  69          * @param int $i
  70          * @return string|null
  71          */
  72         public function getClosing( $i = null ) {
  73                 if ( $i === null ) {
  74                         return $this->closing;
  75                 }
  76                 if ( array_key_exists( $i, $this->closing ) ) {
  77                         return $this->closing[$i];
  78                 }
  79                 return null;
  80         }
  81
  82         abstract public function reverse();
  83
  84         /**
  85          * @return int
  86          */
  87         public function norig() {
  88                 return $this->orig ? count( $this->orig ) : 0;
  89         }
  90
  91         /**
  92          * @return int
  93          */
  94         public function nclosing() {
  95                 return $this->closing ? count( $this->closing ) : 0;
  96         }
  97 }
  98
  99 /**
 100  * Extends DiffOp. Used to mark strings that have been
 101  * copied from one string array to the other.
 102  *
 103  * @private
 104  * @ingroup DifferenceEngine
 105  */
 106 class DiffOpCopy extends DiffOp {
 107         public $type = 'copy';
 108
 109         public function __construct( $orig, $closing = false ) {
 110                 if ( !is_array( $closing ) ) {
 111                         $closing = $orig;
 112                 }
 113                 $this->orig = $orig;
 114                 $this->closing = $closing;
 115         }
 116
 117         /**
 118          * @return DiffOpCopy
 119          */
 120         public function reverse() {
 121                 return new DiffOpCopy( $this->closing, $this->orig );
 122         }
 123 }
 124
 125 /**
 126  * Extends DiffOp. Used to mark strings that have been
 127  * deleted from the first string array.
 128  *
 129  * @private
 130  * @ingroup DifferenceEngine
 131  */
 132 class DiffOpDelete extends DiffOp {
 133         public $type = 'delete';
 134
 135         public function __construct( $lines ) {
 136                 $this->orig = $lines;
 137                 $this->closing = false;
 138         }
 139
 140         /**
 141          * @return DiffOpAdd
 142          */
 143         public function reverse() {
 144                 return new DiffOpAdd( $this->orig );
 145         }
 146 }
 147
 148 /**
 149  * Extends DiffOp. Used to mark strings that have been
 150  * added from the first string array.
 151  *
 152  * @private
 153  * @ingroup DifferenceEngine
 154  */
 155 class DiffOpAdd extends DiffOp {
 156         public $type = 'add';
 157
 158         public function __construct( $lines ) {
 159                 $this->closing = $lines;
 160                 $this->orig = false;
 161         }
 162
 163         /**
 164          * @return DiffOpDelete
 165          */
 166         public function reverse() {
 167                 return new DiffOpDelete( $this->closing );
 168         }
 169 }
 170
 171 /**
 172  * Extends DiffOp. Used to mark strings that have been
 173  * changed from the first string array (both added and subtracted).
 174  *
 175  * @private
 176  * @ingroup DifferenceEngine
 177  */
 178 class DiffOpChange extends DiffOp {
 179         public $type = 'change';
 180
 181         public function __construct( $orig, $closing ) {
 182                 $this->orig = $orig;
 183                 $this->closing = $closing;
 184         }
 185
 186         /**
 187          * @return DiffOpChange
 188          */
 189         public function reverse() {
 190                 return new DiffOpChange( $this->closing, $this->orig );
 191         }
 192 }
 193
 194 /**
 195  * Class representing a 'diff' between two sequences of strings.
 196  * @todo document
 197  * @private
 198  * @ingroup DifferenceEngine
 199  */
 200 class Diff {
 201
 202         /**
 203          * @var DiffOp[]
 204          */
 205         public $edits;
 206
 207         /**
 208          * @var int If this diff complexity is exceeded, a ComplexityException is thrown
 209          *          0 means no limit.
 210          */
 211         protected $bailoutComplexity = 0;
 212
 213         /**
 214          * Constructor.
 215          * Computes diff between sequences of strings.
 216          *
 217          * @param string[] $from_lines An array of strings.
 218          *   Typically these are lines from a file.
 219          * @param string[] $to_lines An array of strings.
 220          * @throws \MediaWiki\Diff\ComplexityException
 221          */
 222         public function __construct( $from_lines, $to_lines ) {
 223                 $eng = new DiffEngine;
 224                 $eng->setBailoutComplexity( $this->bailoutComplexity );
 225                 $this->edits = $eng->diff( $from_lines, $to_lines );
 226         }
 227
 228         /**
 229          * @return DiffOp[]
 230          */
 231         public function getEdits() {
 232                 return $this->edits;
 233         }
 234
 235         /**
 236          * Compute reversed Diff.
 237          *
 238          * SYNOPSIS:
 239          *
 240          *    $diff = new Diff($lines1, $lines2);
 241          *    $rev = $diff->reverse();
 242          *
 243          * @return Object A Diff object representing the inverse of the
 244          *   original diff.
 245          */
 246         public function reverse() {
 247                 $rev = $this;
 248                 $rev->edits = [];
 249                 /** @var DiffOp $edit */
 250                 foreach ( $this->edits as $edit ) {
 251                         $rev->edits[] = $edit->reverse();
 252                 }
 253
 254                 return $rev;
 255         }
 256
 257         /**
 258          * Check for empty diff.
 259          *
 260          * @return bool True if two sequences were identical.
 261          */
 262         public function isEmpty() {
 263                 foreach ( $this->edits as $edit ) {
 264                         if ( $edit->type != 'copy' ) {
 265                                 return false;
 266                         }
 267                 }
 268
 269                 return true;
 270         }
 271
 272         /**
 273          * Compute the length of the Longest Common Subsequence (LCS).
 274          *
 275          * This is mostly for diagnostic purposed.
 276          *
 277          * @return int The length of the LCS.
 278          */
 279         public function lcs() {
 280                 $lcs = 0;
 281                 foreach ( $this->edits as $edit ) {
 282                         if ( $edit->type == 'copy' ) {
 283                                 $lcs += count( $edit->orig );
 284                         }
 285                 }
 286
 287                 return $lcs;
 288         }
 289
 290         /**
 291          * Get the original set of lines.
 292          *
 293          * This reconstructs the $from_lines parameter passed to the
 294          * constructor.
 295          *
 296          * @return string[] The original sequence of strings.
 297          */
 298         public function orig() {
 299                 $lines = [];
 300
 301                 foreach ( $this->edits as $edit ) {
 302                         if ( $edit->orig ) {
 303                                 array_splice( $lines, count( $lines ), 0, $edit->orig );
 304                         }
 305                 }
 306
 307                 return $lines;
 308         }
 309
 310         /**
 311          * Get the closing set of lines.
 312          *
 313          * This reconstructs the $to_lines parameter passed to the
 314          * constructor.
 315          *
 316          * @return string[] The sequence of strings.
 317          */
 318         public function closing() {
 319                 $lines = [];
 320
 321                 foreach ( $this->edits as $edit ) {
 322                         if ( $edit->closing ) {
 323                                 array_splice( $lines, count( $lines ), 0, $edit->closing );
 324                         }
 325                 }
 326
 327                 return $lines;
 328         }
 329 }
 330
 331 /**
 332  * @deprecated Alias for WordAccumulator, to be soon removed
 333  */
 334 class HWLDFWordAccumulator extends MediaWiki\Diff\WordAccumulator {
 335 }