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[]|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          * Computes diff between sequences of strings.
 215          *
 216          * @param string[] $from_lines An array of strings.
 217          *   Typically these are lines from a file.
 218          * @param string[] $to_lines An array of strings.
 219          * @throws \MediaWiki\Diff\ComplexityException
 220          */
 221         public function __construct( $from_lines, $to_lines ) {
 222                 $eng = new DiffEngine;
 223                 $eng->setBailoutComplexity( $this->bailoutComplexity );
 224                 $this->edits = $eng->diff( $from_lines, $to_lines );
 225         }
 226
 227         /**
 228          * @return DiffOp[]
 229          */
 230         public function getEdits() {
 231                 return $this->edits;
 232         }
 233
 234         /**
 235          * Compute reversed Diff.
 236          *
 237          * SYNOPSIS:
 238          *
 239          *    $diff = new Diff($lines1, $lines2);
 240          *    $rev = $diff->reverse();
 241          *
 242          * @return Object A Diff object representing the inverse of the
 243          *   original diff.
 244          */
 245         public function reverse() {
 246                 $rev = $this;
 247                 $rev->edits = [];
 248                 /** @var DiffOp $edit */
 249                 foreach ( $this->edits as $edit ) {
 250                         $rev->edits[] = $edit->reverse();
 251                 }
 252
 253                 return $rev;
 254         }
 255
 256         /**
 257          * Check for empty diff.
 258          *
 259          * @return bool True if two sequences were identical.
 260          */
 261         public function isEmpty() {
 262                 foreach ( $this->edits as $edit ) {
 263                         if ( $edit->type != 'copy' ) {
 264                                 return false;
 265                         }
 266                 }
 267
 268                 return true;
 269         }
 270
 271         /**
 272          * Compute the length of the Longest Common Subsequence (LCS).
 273          *
 274          * This is mostly for diagnostic purposed.
 275          *
 276          * @return int The length of the LCS.
 277          */
 278         public function lcs() {
 279                 $lcs = 0;
 280                 foreach ( $this->edits as $edit ) {
 281                         if ( $edit->type == 'copy' ) {
 282                                 $lcs += count( $edit->orig );
 283                         }
 284                 }
 285
 286                 return $lcs;
 287         }
 288
 289         /**
 290          * Get the original set of lines.
 291          *
 292          * This reconstructs the $from_lines parameter passed to the
 293          * constructor.
 294          *
 295          * @return string[] The original sequence of strings.
 296          */
 297         public function orig() {
 298                 $lines = [];
 299
 300                 foreach ( $this->edits as $edit ) {
 301                         if ( $edit->orig ) {
 302                                 array_splice( $lines, count( $lines ), 0, $edit->orig );
 303                         }
 304                 }
 305
 306                 return $lines;
 307         }
 308
 309         /**
 310          * Get the closing set of lines.
 311          *
 312          * This reconstructs the $to_lines parameter passed to the
 313          * constructor.
 314          *
 315          * @return string[] The sequence of strings.
 316          */
 317         public function closing() {
 318                 $lines = [];
 319
 320                 foreach ( $this->edits as $edit ) {
 321                         if ( $edit->closing ) {
 322                                 array_splice( $lines, count( $lines ), 0, $edit->closing );
 323                         }
 324                 }
 325
 326                 return $lines;
 327         }
 328 }
 329
 330 /**
 331  * @deprecated Alias for WordAccumulator, to be soon removed
 332  */
 333 class HWLDFWordAccumulator extends MediaWiki\Diff\WordAccumulator {
 334 }