includes/diff/Diff.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  */
  26
  27 /**
  28  * Class representing a 'diff' between two sequences of strings.
  29  * @private
  30  * @ingroup DifferenceEngine
  31  */
  32 class Diff {
  33
  34         /**
  35          * @var DiffOp[]
  36          */
  37         public $edits;
  38
  39         /**
  40          * @var int If this diff complexity is exceeded, a ComplexityException is thrown
  41          *          0 means no limit.
  42          */
  43         protected $bailoutComplexity = 0;
  44
  45         /**
  46          * Computes diff between sequences of strings.
  47          *
  48          * @param string[] $from_lines An array of strings.
  49          *   Typically these are lines from a file.
  50          * @param string[] $to_lines An array of strings.
  51          * @throws \MediaWiki\Diff\ComplexityException
  52          */
  53         public function __construct( $from_lines, $to_lines ) {
  54                 $eng = new DiffEngine;
  55                 $eng->setBailoutComplexity( $this->bailoutComplexity );
  56                 $this->edits = $eng->diff( $from_lines, $to_lines );
  57         }
  58
  59         /**
  60          * @return DiffOp[]
  61          */
  62         public function getEdits() {
  63                 return $this->edits;
  64         }
  65
  66         /**
  67          * Compute reversed Diff.
  68          *
  69          * SYNOPSIS:
  70          *
  71          *    $diff = new Diff($lines1, $lines2);
  72          *    $rev = $diff->reverse();
  73          *
  74          * @return Object A Diff object representing the inverse of the
  75          *   original diff.
  76          */
  77         public function reverse() {
  78                 $rev = $this;
  79                 $rev->edits = [];
  80                 /** @var DiffOp $edit */
  81                 foreach ( $this->edits as $edit ) {
  82                         $rev->edits[] = $edit->reverse();
  83                 }
  84
  85                 return $rev;
  86         }
  87
  88         /**
  89          * Check for empty diff.
  90          *
  91          * @return bool True if two sequences were identical.
  92          */
  93         public function isEmpty() {
  94                 foreach ( $this->edits as $edit ) {
  95                         if ( $edit->type != 'copy' ) {
  96                                 return false;
  97                         }
  98                 }
  99
 100                 return true;
 101         }
 102
 103         /**
 104          * Compute the length of the Longest Common Subsequence (LCS).
 105          *
 106          * This is mostly for diagnostic purposed.
 107          *
 108          * @return int The length of the LCS.
 109          */
 110         public function lcs() {
 111                 $lcs = 0;
 112                 foreach ( $this->edits as $edit ) {
 113                         if ( $edit->type == 'copy' ) {
 114                                 $lcs += count( $edit->orig );
 115                         }
 116                 }
 117
 118                 return $lcs;
 119         }
 120
 121         /**
 122          * Get the original set of lines.
 123          *
 124          * This reconstructs the $from_lines parameter passed to the
 125          * constructor.
 126          *
 127          * @return string[] The original sequence of strings.
 128          */
 129         public function orig() {
 130                 $lines = [];
 131
 132                 foreach ( $this->edits as $edit ) {
 133                         if ( $edit->orig ) {
 134                                 array_splice( $lines, count( $lines ), 0, $edit->orig );
 135                         }
 136                 }
 137
 138                 return $lines;
 139         }
 140
 141         /**
 142          * Get the closing set of lines.
 143          *
 144          * This reconstructs the $to_lines parameter passed to the
 145          * constructor.
 146          *
 147          * @return string[] The sequence of strings.
 148          */
 149         public function closing() {
 150                 $lines = [];
 151
 152                 foreach ( $this->edits as $edit ) {
 153                         if ( $edit->closing ) {
 154                                 array_splice( $lines, count( $lines ), 0, $edit->closing );
 155                         }
 156                 }
 157
 158                 return $lines;
 159         }
 160 }