Text_Diff
[ class tree: Text_Diff ] [ index: Text_Diff ] [ all elements ]

Source for file Diff.php

Documentation is available at Diff.php

  1. <?php
  2. /**
  3.  * Text_Diff
  4.  *
  5.  * General API for generating and formatting diffs - the differences between
  6.  * two sequences of strings.
  7.  *
  8.  * The PHP diff code used in this package was originally written by Geoffrey
  9.  * T. Dairiki and is used with his permission.
  10.  *
  11.  * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $
  12.  *
  13.  * @package Text_Diff
  14.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  15.  */
  16. class Text_Diff {
  17.  
  18.     /**
  19.      * Array of changes.
  20.      *
  21.      * @var array 
  22.      */
  23.     var $_edits;
  24.  
  25.     /**
  26.      * Computes diffs between sequences of strings.
  27.      *
  28.      * @param array $from_lines  An array of strings.  Typically these are
  29.      *                            lines from a file.
  30.      * @param array $to_lines    An array of strings.
  31.      */
  32.     function Text_Diff($from_lines$to_lines)
  33.     {
  34.         array_walk($from_linesarray($this'_trimNewlines'));
  35.         array_walk($to_linesarray($this'_trimNewlines'));
  36.  
  37.         if (extension_loaded('xdiff')) {
  38.             $engine &new Text_Diff_Engine_xdiff();
  39.         else {
  40.             $engine &new Text_Diff_Engine_native();
  41.         }
  42.  
  43.         $this->_edits $engine->diff($from_lines$to_lines);
  44.     }
  45.  
  46.     /**
  47.      * Returns the array of differences.
  48.      */
  49.     function getDiff()
  50.     {
  51.         return $this->_edits;
  52.     }
  53.  
  54.     /**
  55.      * Computes a reversed diff.
  56.      *
  57.      * Example:
  58.      * <code>
  59.      * $diff = &new Text_Diff($lines1, $lines2);
  60.      * $rev = $diff->reverse();
  61.      * </code>
  62.      *
  63.      * @return Text_Diff  A Diff object representing the inverse of the
  64.      *                     original diff.  Note that we purposely don't return a
  65.      *                     reference here, since this essentially is a clone()
  66.      *                     method.
  67.      */
  68.     function reverse()
  69.     {
  70.         if (version_compare(zend_version()'2''>')) {
  71.             $rev = clone($obj);
  72.         else {
  73.             $rev $this;
  74.         }
  75.         $rev->_edits = array();
  76.         foreach ($this->_edits as $edit{
  77.             $rev->_edits[$edit->reverse();
  78.         }
  79.         return $rev;
  80.     }
  81.  
  82.     /**
  83.      * Checks for an empty diff.
  84.      *
  85.      * @return boolean  True if two sequences were identical.
  86.      */
  87.     function isEmpty()
  88.     {
  89.         foreach ($this->_edits as $edit{
  90.             if (!is_a($edit'Text_Diff_Op_copy')) {
  91.                 return false;
  92.             }
  93.         }
  94.         return true;
  95.     }
  96.  
  97.     /**
  98.      * Computes the length of the Longest Common Subsequence (LCS).
  99.      *
  100.      * This is mostly for diagnostic purposes.
  101.      *
  102.      * @return integer  The length of the LCS.
  103.      */
  104.     function lcs()
  105.     {
  106.         $lcs = 0;
  107.         foreach ($this->_edits as $edit{
  108.             if (is_a($edit'Text_Diff_Op_copy')) {
  109.                 $lcs += count($edit->orig);
  110.             }
  111.         }
  112.         return $lcs;
  113.     }
  114.  
  115.     /**
  116.      * Gets the original set of lines.
  117.      *
  118.      * This reconstructs the $from_lines parameter passed to the constructor.
  119.      *
  120.      * @return array  The original sequence of strings.
  121.      */
  122.     function getOriginal()
  123.     {
  124.         $lines = array();
  125.         foreach ($this->_edits as $edit{
  126.             if ($edit->orig{
  127.                 array_splice($linescount($lines)0$edit->orig);
  128.             }
  129.         }
  130.         return $lines;
  131.     }
  132.  
  133.     /**
  134.      * Gets the final set of lines.
  135.      *
  136.      * This reconstructs the $to_lines parameter passed to the constructor.
  137.      *
  138.      * @return array  The sequence of strings.
  139.      */
  140.     function getFinal()
  141.     {
  142.         $lines = array();
  143.         foreach ($this->_edits as $edit{
  144.             if ($edit->final{
  145.                 array_splice($linescount($lines)0$edit->final);
  146.             }
  147.         }
  148.         return $lines;
  149.     }
  150.  
  151.     /**
  152.      * Removes trailing newlines from a line of text. This is meant to be used
  153.      * with array_walk().
  154.      *
  155.      * @param string $line  The line to trim.
  156.      * @param integer $key  The index of the line in the array. Not used.
  157.      */
  158.     function _trimNewlines(&$line$key)
  159.     {
  160.         $line str_replace(array("\n""\r")''$line);
  161.     }
  162.  
  163.     /**
  164.      * Checks a diff for validity.
  165.      *
  166.      * This is here only for debugging purposes.
  167.      */
  168.     function _check($from_lines$to_lines)
  169.     {
  170.         if (serialize($from_lines!= serialize($this->getOriginal())) {
  171.             trigger_error("Reconstructed original doesn't match"E_USER_ERROR);
  172.         }
  173.         if (serialize($to_lines!= serialize($this->getFinal())) {
  174.             trigger_error("Reconstructed final doesn't match"E_USER_ERROR);
  175.         }
  176.  
  177.         $rev $this->reverse();
  178.         if (serialize($to_lines!= serialize($rev->getOriginal())) {
  179.             trigger_error("Reversed original doesn't match"E_USER_ERROR);
  180.         }
  181.         if (serialize($from_lines!= serialize($rev->getFinal())) {
  182.             trigger_error("Reversed final doesn't match"E_USER_ERROR);
  183.         }
  184.  
  185.         $prevtype = null;
  186.         foreach ($this->_edits as $edit{
  187.             if ($prevtype == get_class($edit)) {
  188.                 trigger_error("Edit sequence is non-optimal"E_USER_ERROR);
  189.             }
  190.             $prevtype get_class($edit);
  191.         }
  192.  
  193.         return true;
  194.     }
  195.  
  196. }
  197.  
  198. /**
  199.  * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $
  200.  *
  201.  * @package Text_Diff
  202.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  203.  */
  204. class Text_MappedDiff extends Text_Diff {
  205.  
  206.     /**
  207.      * Computes a diff between sequences of strings.
  208.      *
  209.      * This can be used to compute things like case-insensitve diffs, or diffs
  210.      * which ignore changes in white-space.
  211.      *
  212.      * @param array $from_lines         An array of strings.
  213.      * @param array $to_lines           An array of strings.
  214.      * @param array $mapped_from_lines  This array should have the same size
  215.      *                                   number of elements as $from_lines.  The
  216.      *                                   elements in $mapped_from_lines and
  217.      *                                   $mapped_to_lines are what is actually
  218.      *                                   compared when computing the diff.
  219.      * @param array $mapped_to_lines    This array should have the same number
  220.      *                                   of elements as $to_lines.
  221.      */
  222.     function Text_MappedDiff($from_lines$to_lines,
  223.                              $mapped_from_lines$mapped_to_lines)
  224.     {
  225.         assert(count($from_lines== count($mapped_from_lines));
  226.         assert(count($to_lines== count($mapped_to_lines));
  227.  
  228.         parent::Text_Diff($mapped_from_lines$mapped_to_lines);
  229.  
  230.         $xi $yi = 0;
  231.         for ($i = 0; $i count($this->_edits)$i++{
  232.             $orig &$this->_edits[$i]->orig;
  233.             if (is_array($orig)) {
  234.                 $orig array_slice($from_lines$xicount($orig));
  235.                 $xi += count($orig);
  236.             }
  237.  
  238.             $final &$this->_edits[$i]->final;
  239.             if (is_array($final)) {
  240.                 $final array_slice($to_lines$yicount($final));
  241.                 $yi += count($final);
  242.             }
  243.         }
  244.     }
  245.  
  246. }
  247.  
  248. /**
  249.  * Class used internally by Diff to actually compute the diffs.  This class
  250.  * uses the xdiff PECL package (http://pecl.php.net/package/xdiff) to compute
  251.  * the differences between the two input arrays.
  252.  *
  253.  * @author  Jon Parise <jon@horde.org>
  254.  * @package Text_Diff
  255.  *
  256.  * @access private
  257.  */
  258. class Text_Diff_Engine_xdiff {
  259.  
  260.     function diff($from_lines$to_lines)
  261.     {
  262.         /* Convert the two input arrays into strings for xdiff processing. */
  263.         $from_string implode("\n"$from_lines);
  264.         $to_string implode("\n"$to_lines);
  265.  
  266.         /* Diff the two strings and convert the result to an array. */
  267.         $diff = xdiff_string_diff($from_string$to_stringcount($to_lines));
  268.         $diff explode("\n"$diff);
  269.  
  270.         /* Walk through the diff one line at a time.  We build the $edits
  271.          * array of diff operations by reading the first character of the
  272.          * xdiff output (which is in the "unified diff" format).
  273.          *
  274.          * Note that we don't have enough information to detect "changed"
  275.          * lines using this approach, so we can't add Text_Diff_Op_changed
  276.          * instances to the $edits array.  The result is still perfectly
  277.          * valid, albeit a little less descriptive and efficient. */
  278.         $edits = array();
  279.         foreach ($diff as $line{
  280.             switch ($line[0]{
  281.             case ' ':
  282.                 $edits[&new Text_Diff_Op_copy(array(substr($line1)));
  283.                 break;
  284.  
  285.             case '+':
  286.                 $edits[&new Text_Diff_Op_add(array(substr($line1)));
  287.                 break;
  288.  
  289.             case '-':
  290.                 $edits[&new Text_Diff_Op_delete(array(substr($line1)));
  291.                 break;
  292.             }
  293.         }
  294.  
  295.         return $edits;
  296.     }
  297.  
  298. }
  299.  
  300. /**
  301.  * Class used internally by Diff to actually compute the diffs.  This class is
  302.  * implemented using native PHP code.
  303.  *
  304.  * The algorithm used here is mostly lifted from the perl module
  305.  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
  306.  * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
  307.  *
  308.  * More ideas are taken from:
  309.  * http://www.ics.uci.edu/~eppstein/161/960229.html
  310.  *
  311.  * Some ideas (and a bit of code) are taken from analyze.c, of GNU
  312.  * diffutils-2.7, which can be found at:
  313.  * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
  314.  *
  315.  * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
  316.  * Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this
  317.  * code was written by him, and is used/adapted with his permission.
  318.  *
  319.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  320.  * @package Text_Diff
  321.  *
  322.  * @access private
  323.  */
  324. class Text_Diff_Engine_native {
  325.  
  326.     function diff($from_lines$to_lines)
  327.     {
  328.         $n_from count($from_lines);
  329.         $n_to count($to_lines);
  330.  
  331.         $this->xchanged $this->ychanged = array();
  332.         $this->xv $this->yv = array();
  333.         $this->xind $this->yind = array();
  334.         unset($this->seq);
  335.         unset($this->in_seq);
  336.         unset($this->lcs);
  337.  
  338.         // Skip leading common lines.
  339.         for ($skip = 0; $skip $n_from && $skip $n_to$skip++{
  340.             if ($from_lines[$skip!= $to_lines[$skip]{
  341.                 break;
  342.             }
  343.             $this->xchanged[$skip$this->ychanged[$skip= false;
  344.         }
  345.  
  346.         // Skip trailing common lines.
  347.         $xi $n_from$yi $n_to;
  348.         for ($endskip = 0; --$xi $skip && --$yi $skip$endskip++{
  349.             if ($from_lines[$xi!= $to_lines[$yi]{
  350.                 break;
  351.             }
  352.             $this->xchanged[$xi$this->ychanged[$yi= false;
  353.         }
  354.  
  355.         // Ignore lines which do not exist in both files.
  356.         for ($xi $skip$xi $n_from $endskip$xi++{
  357.             $xhash[$from_lines[$xi]] = 1;
  358.         }
  359.         for ($yi $skip$yi $n_to $endskip$yi++{
  360.             $line $to_lines[$yi];
  361.             if (($this->ychanged[$yi= empty($xhash[$line]))) {
  362.                 continue;
  363.             }
  364.             $yhash[$line= 1;
  365.             $this->yv[$line;
  366.             $this->yind[$yi;
  367.         }
  368.         for ($xi $skip$xi $n_from $endskip$xi++{
  369.             $line $from_lines[$xi];
  370.             if (($this->xchanged[$xi= empty($yhash[$line]))) {
  371.                 continue;
  372.             }
  373.             $this->xv[$line;
  374.             $this->xind[$xi;
  375.         }
  376.  
  377.         // Find the LCS.
  378.         $this->_compareseq(0count($this->xv)0count($this->yv));
  379.  
  380.         // Merge edits when possible.
  381.         $this->_shiftBoundaries($from_lines$this->xchanged$this->ychanged);
  382.         $this->_shiftBoundaries($to_lines$this->ychanged$this->xchanged);
  383.  
  384.         // Compute the edit operations.
  385.         $edits = array();
  386.         $xi $yi = 0;
  387.         while ($xi $n_from || $yi $n_to{
  388.             assert($yi $n_to || $this->xchanged[$xi]);
  389.             assert($xi $n_from || $this->ychanged[$yi]);
  390.  
  391.             // Skip matching "snake".
  392.             $copy = array();
  393.             while ($xi $n_from && $yi $n_to
  394.                    && !$this->xchanged[$xi&& !$this->ychanged[$yi]{
  395.                 $copy[$from_lines[$xi++];
  396.                 ++$yi;
  397.             }
  398.             if ($copy{
  399.                 $edits[&new Text_Diff_Op_copy($copy);
  400.             }
  401.  
  402.             // Find deletes & adds.
  403.             $delete = array();
  404.             while ($xi $n_from && $this->xchanged[$xi]{
  405.                 $delete[$from_lines[$xi++];
  406.             }
  407.  
  408.             $add = array();
  409.             while ($yi $n_to && $this->ychanged[$yi]{
  410.                 $add[$to_lines[$yi++];
  411.             }
  412.  
  413.             if ($delete && $add{
  414.                 $edits[&new Text_Diff_Op_change($delete$add);
  415.             elseif ($delete{
  416.                 $edits[&new Text_Diff_Op_delete($delete);
  417.             elseif ($add{
  418.                 $edits[&new Text_Diff_Op_add($add);
  419.             }
  420.         }
  421.  
  422.         return $edits;
  423.     }
  424.  
  425.     /**
  426.      * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,
  427.      * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized
  428.      * segments.
  429.      *
  430.      * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of
  431.      * NCHUNKS+1 (X, Y) indexes giving the diving points between sub
  432.      * sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),
  433.      * the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==
  434.      * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
  435.      *
  436.      * This function assumes that the first lines of the specified portions of
  437.      * the two files do not match, and likewise that the last lines do not
  438.      * match.  The caller must trim matching lines from the beginning and end
  439.      * of the portions it is going to specify.
  440.      */
  441.     function _diag ($xoff$xlim$yoff$ylim$nchunks)
  442.     {
  443.         $flip = false;
  444.  
  445.         if ($xlim $xoff $ylim $yoff{
  446.             /* Things seems faster (I'm not sure I understand why) when the
  447.              * shortest sequence is in X. */
  448.             $flip = true;
  449.             list ($xoff$xlim$yoff$ylim)
  450.                 = array($yoff$ylim$xoff$xlim);
  451.         }
  452.  
  453.         if ($flip{
  454.             for ($i $ylim - 1; $i >= $yoff$i--{
  455.                 $ymatches[$this->xv[$i]][$i;
  456.             }
  457.         else {
  458.             for ($i $ylim - 1; $i >= $yoff$i--{
  459.                 $ymatches[$this->yv[$i]][$i;
  460.             }
  461.         }
  462.  
  463.         $this->lcs = 0;
  464.         $this->seq[0]$yoff - 1;
  465.         $this->in_seq = array();
  466.         $ymids[0= array();
  467.  
  468.         $numer $xlim $xoff $nchunks - 1;
  469.         $x $xoff;
  470.         for ($chunk = 0; $chunk $nchunks$chunk++{
  471.             if ($chunk > 0{
  472.                 for ($i = 0; $i <= $this->lcs$i++{
  473.                     $ymids[$i][$chunk - 1$this->seq[$i];
  474.                 }
  475.             }
  476.  
  477.             $x1 $xoff + (int)(($numer ($xlim-$xoff)*$chunk$nchunks);
  478.             for ($x $x1$x++{
  479.                 $line $flip $this->yv[$x$this->xv[$x];
  480.                 if (empty($ymatches[$line])) {
  481.                     continue;
  482.                 }
  483.                 $matches $ymatches[$line];
  484.                 foreach ($matches as $y{
  485.                     if (empty($this->in_seq[$y])) {
  486.                         $k $this->_lcsPos($y);
  487.                         assert($k > 0);
  488.                         $ymids[$k$ymids[$k - 1];
  489.                         break;
  490.                     }
  491.                 }
  492.  
  493.                 while (list($junk$yeach($matches)) {
  494.                     if ($y $this->seq[$k - 1]{
  495.                         assert($y $this->seq[$k]);
  496.                         /* Optimization: this is a common case: next match is
  497.                          * just replacing previous match. */
  498.                         $this->in_seq[$this->seq[$k]] = false;
  499.                         $this->seq[$k$y;
  500.                         $this->in_seq[$y= 1;
  501.                     elseif (empty($this->in_seq[$y])) {
  502.                         $k $this->_lcsPos($y);
  503.                         assert($k > 0);
  504.                         $ymids[$k$ymids[$k - 1];
  505.                     }
  506.                 }
  507.             }
  508.         }
  509.  
  510.         $seps[$flip ? array($yoff$xoff: array($xoff$yoff);
  511.         $ymid $ymids[$this->lcs];
  512.         for ($n = 0; $n $nchunks - 1; $n++{
  513.             $x1 $xoff + (int)(($numer ($xlim $xoff$n$nchunks);
  514.             $y1 $ymid[$n+ 1;
  515.             $seps[$flip ? array($y1$x1: array($x1$y1);
  516.         }
  517.         $seps[$flip ? array($ylim$xlim: array($xlim$ylim);
  518.  
  519.         return array($this->lcs$seps);
  520.     }
  521.  
  522.     function _lcsPos($ypos)
  523.     {
  524.         $end $this->lcs;
  525.         if ($end == 0 || $ypos $this->seq[$end]{
  526.             $this->seq[++$this->lcs$ypos;
  527.             $this->in_seq[$ypos= 1;
  528.             return $this->lcs;
  529.         }
  530.  
  531.         $beg = 1;
  532.         while ($beg $end{
  533.             $mid = (int)(($beg $end/ 2);
  534.             if ($ypos $this->seq[$mid]{
  535.                 $beg $mid + 1;
  536.             else {
  537.                 $end $mid;
  538.             }
  539.         }
  540.  
  541.         assert($ypos != $this->seq[$end]);
  542.  
  543.         $this->in_seq[$this->seq[$end]] = false;
  544.         $this->seq[$end$ypos;
  545.         $this->in_seq[$ypos= 1;
  546.         return $end;
  547.     }
  548.  
  549.     /**
  550.      * Finds LCS of two sequences.
  551.      *
  552.      * The results are recorded in the vectors $this->{x,y}changed[], by
  553.      * storing a 1 in the element for each line that is an insertion or
  554.      * deletion (ie. is not in the LCS).
  555.      *
  556.      * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1.
  557.      *
  558.      * Note that XLIM, YLIM are exclusive bounds.  All line numbers are
  559.      * origin-0 and discarded lines are not counted.
  560.      */
  561.     function _compareseq ($xoff$xlim$yoff$ylim)
  562.     {
  563.         /* Slide down the bottom initial diagonal. */
  564.         while ($xoff $xlim && $yoff $ylim
  565.                && $this->xv[$xoff== $this->yv[$yoff]{
  566.             ++$xoff;
  567.             ++$yoff;
  568.         }
  569.  
  570.         /* Slide up the top initial diagonal. */
  571.         while ($xlim $xoff && $ylim $yoff
  572.                && $this->xv[$xlim - 1== $this->yv[$ylim - 1]{
  573.             --$xlim;
  574.             --$ylim;
  575.         }
  576.  
  577.         if ($xoff == $xlim || $yoff == $ylim{
  578.             $lcs = 0;
  579.         else {
  580.             /* This is ad hoc but seems to work well.  $nchunks =
  581.              * sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); $nchunks =
  582.              * max(2,min(8,(int)$nchunks)); */
  583.             $nchunks min(7$xlim $xoff$ylim $yoff+ 1;
  584.             list($lcs$seps)
  585.                 = $this->_diag($xoff$xlim$yoff$ylim$nchunks);
  586.         }
  587.  
  588.         if ($lcs == 0{
  589.             /* X and Y sequences have no common subsequence: mark all
  590.              * changed. */
  591.             while ($yoff $ylim{
  592.                 $this->ychanged[$this->yind[$yoff++]] = 1;
  593.             }
  594.             while ($xoff $xlim{
  595.                 $this->xchanged[$this->xind[$xoff++]] = 1;
  596.             }
  597.         else {
  598.             /* Use the partitions to split this problem into subproblems. */
  599.             reset($seps);
  600.             $pt1 $seps[0];
  601.             while ($pt2 next($seps)) {
  602.                 $this->_compareseq ($pt1[0]$pt2[0]$pt1[1]$pt2[1]);
  603.                 $pt1 $pt2;
  604.             }
  605.         }
  606.     }
  607.  
  608.     /**
  609.      * Adjusts inserts/deletes of identical lines to join changes as much as
  610.      * possible.
  611.      *
  612.      * We do something when a run of changed lines include a line at one end
  613.      * and has an excluded, identical line at the other.  We are free to
  614.      * choose which identical line is included.  `compareseq' usually chooses
  615.      * the one at the beginning, but usually it is cleaner to consider the
  616.      * following identical line to be the "change".
  617.      *
  618.      * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
  619.      */
  620.     function _shiftBoundaries($lines&$changed$other_changed)
  621.     {
  622.         $i = 0;
  623.         $j = 0;
  624.  
  625.         assert('count($lines) == count($changed)');
  626.         $len count($lines);
  627.         $other_len count($other_changed);
  628.  
  629.         while (1{
  630.             /* Scan forward to find the beginning of another run of
  631.              * changes. Also keep track of the corresponding point in the
  632.              * other file.
  633.              *
  634.              * Throughout this code, $i and $j are adjusted together so that
  635.              * the first $i elements of $changed and the first $j elements of
  636.              * $other_changed both contain the same number of zeros (unchanged
  637.              * lines).
  638.              *
  639.              * Furthermore, $j is always kept so that $j == $other_len or
  640.              * $other_changed[$j] == false. */
  641.             while ($j $other_len && $other_changed[$j]{
  642.                 $j++;
  643.             }
  644.  
  645.             while ($i $len && $changed[$i]{
  646.                 assert('$j < $other_len && ! $other_changed[$j]');
  647.                 $i++; $j++;
  648.                 while ($j $other_len && $other_changed[$j]{
  649.                     $j++;
  650.                 }
  651.             }
  652.  
  653.             if ($i == $len{
  654.                 break;
  655.             }
  656.  
  657.             $start $i;
  658.  
  659.             /* Find the end of this run of changes. */
  660.             while (++$i $len && $changed[$i]{
  661.                 continue;
  662.             }
  663.  
  664.             do {
  665.                 /* Record the length of this run of changes, so that we can
  666.                  * later determine whether the run has grown. */
  667.                 $runlength $i $start;
  668.  
  669.                 /* Move the changed region back, so long as the previous
  670.                  * unchanged line matches the last changed one.  This merges
  671.                  * with previous changed regions. */
  672.                 while ($start > 0 && $lines[$start - 1== $lines[$i - 1]{
  673.                     $changed[--$start= 1;
  674.                     $changed[--$i= false;
  675.                     while ($start > 0 && $changed[$start - 1]{
  676.                         $start--;
  677.                     }
  678.                     assert('$j > 0');
  679.                     while ($other_changed[--$j]{
  680.                         continue;
  681.                     }
  682.                     assert('$j >= 0 && !$other_changed[$j]');
  683.                 }
  684.  
  685.                 /* Set CORRESPONDING to the end of the changed run, at the
  686.                  * last point where it corresponds to a changed run in the
  687.                  * other file. CORRESPONDING == LEN means no such point has
  688.                  * been found. */
  689.                 $corresponding $j $other_len $i $len;
  690.  
  691.                 /* Move the changed region forward, so long as the first
  692.                  * changed line matches the following unchanged one.  This
  693.                  * merges with following changed regions.  Do this second, so
  694.                  * that if there are no merges, the changed region is moved
  695.                  * forward as far as possible. */
  696.                 while ($i $len && $lines[$start== $lines[$i]{
  697.                     $changed[$start++= false;
  698.                     $changed[$i++= 1;
  699.                     while ($i $len && $changed[$i]{
  700.                         $i++;
  701.                     }
  702.  
  703.                     assert('$j < $other_len && ! $other_changed[$j]');
  704.                     $j++;
  705.                     if ($j $other_len && $other_changed[$j]{
  706.                         $corresponding $i;
  707.                         while ($j $other_len && $other_changed[$j]{
  708.                             $j++;
  709.                         }
  710.                     }
  711.                 }
  712.             while ($runlength != $i $start);
  713.  
  714.             /* If possible, move the fully-merged run of changes back to a
  715.              * corresponding run in the other file. */
  716.             while ($corresponding $i{
  717.                 $changed[--$start= 1;
  718.                 $changed[--$i= 0;
  719.                 assert('$j > 0');
  720.                 while ($other_changed[--$j]{
  721.                     continue;
  722.                 }
  723.                 assert('$j >= 0 && !$other_changed[$j]');
  724.             }
  725.         }
  726.     }
  727.  
  728. }
  729.  
  730. /**
  731.  * @package Text_Diff
  732.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  733.  *
  734.  * @access private
  735.  */
  736. class Text_Diff_Op {
  737.  
  738.     var $orig;
  739.     var $final;
  740.  
  741.     function reverse()
  742.     {
  743.         trigger_error('Abstract method'E_USER_ERROR);
  744.     }
  745.  
  746.     function norig()
  747.     {
  748.         return $this->orig count($this->orig: 0;
  749.     }
  750.  
  751.     function nfinal()
  752.     {
  753.         return $this->final count($this->final: 0;
  754.     }
  755.  
  756. }
  757.  
  758. /**
  759.  * @package Text_Diff
  760.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  761.  *
  762.  * @access private
  763.  */
  764. class Text_Diff_Op_copy extends Text_Diff_Op {
  765.  
  766.     function Text_Diff_Op_copy($orig$final = false)
  767.     {
  768.         if (!is_array($final)) {
  769.             $final $orig;
  770.         }
  771.         $this->orig $orig;
  772.         $this->final $final;
  773.     }
  774.  
  775.     function &reverse()
  776.     {
  777.         return $reverse &new Text_Diff_Op_copy($this->final$this->orig);
  778.     }
  779.  
  780. }
  781.  
  782. /**
  783.  * @package Text_Diff
  784.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  785.  *
  786.  * @access private
  787.  */
  788. class Text_Diff_Op_delete extends Text_Diff_Op {
  789.  
  790.     function Text_Diff_Op_delete($lines)
  791.     {
  792.         $this->orig $lines;
  793.         $this->final = false;
  794.     }
  795.  
  796.     function &reverse()
  797.     {
  798.         return $reverse &new Text_Diff_Op_add($this->orig);
  799.     }
  800.  
  801. }
  802.  
  803. /**
  804.  * @package Text_Diff
  805.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  806.  *
  807.  * @access private
  808.  */
  809. class Text_Diff_Op_add extends Text_Diff_Op {
  810.  
  811.     function Text_Diff_Op_add($lines)
  812.     {
  813.         $this->final $lines;
  814.         $this->orig = false;
  815.     }
  816.  
  817.     function &reverse()
  818.     {
  819.         return $reverse &new Text_Diff_Op_delete($this->final);
  820.     }
  821.  
  822. }
  823.  
  824. /**
  825.  * @package Text_Diff
  826.  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  827.  *
  828.  * @access private
  829.  */
  830. class Text_Diff_Op_change extends Text_Diff_Op {
  831.  
  832.     function Text_Diff_Op_change($orig$final)
  833.     {
  834.         $this->orig $orig;
  835.         $this->final $final;
  836.     }
  837.  
  838.     function &reverse()
  839.     {
  840.         return $reverse &new Text_Diff_Op_change($this->final$this->orig);
  841.     }
  842.  
  843. }

Documentation generated on Mon, 11 Mar 2019 14:16:38 -0400 by phpDocumentor 1.4.4. PEAR Logo Copyright © PHP Group 2004.