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