<?php/** * $Horde: framework/Text_Diff/Diff/Engine/native.php,v 1.10 2008/01/04 10:27:53 jan Exp $ * * Class used internally by Text_Diff to actually compute the diffs. This * class is implemented using native PHP code. * * The algorithm used here is mostly lifted from the perl module * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip * * More ideas are taken from: http://www.ics.uci.edu/~eppstein/161/960229.html * * Some ideas (and a bit of code) are taken from analyze.c, of GNU * diffutils-2.7, which can be found at: * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz * * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from * Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this * code was written by him, and is used/adapted with his permission. * * Copyright 2004-2008 The Horde Project (http://www.horde.org/) * * See the enclosed file COPYING for license information (LGPL). If you did * not receive this file, see http://opensource.org/licenses/lgpl-license.php. * * @author  Geoffrey T. Dairiki <dairiki@dairiki.org> * @package Text_Diff */class Text_Diff_Engine_native {    function diff($from_lines, $to_lines)    {        array_walk($from_lines, array('Text_Diff', 'trimNewlines'));        array_walk($to_lines, array('Text_Diff', 'trimNewlines'));        $n_from = count($from_lines);        $n_to = count($to_lines);        $this->xchanged = $this->ychanged = array();        $this->xv = $this->yv = array();        $this->xind = $this->yind = array();        unset($this->seq);        unset($this->in_seq);        unset($this->lcs);        // Skip leading common lines.        for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {            if ($from_lines[$skip] !== $to_lines[$skip]) {                break;            }            $this->xchanged[$skip] = $this->ychanged[$skip] = false;        }        // Skip trailing common lines.        $xi = $n_from; $yi = $n_to;        for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {            if ($from_lines[$xi] !== $to_lines[$yi]) {                break;            }            $this->xchanged[$xi] = $this->ychanged[$yi] = false;        }        // Ignore lines which do not exist in both files.        for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {            $xhash[$from_lines[$xi]] = 1;        }        for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {            $line = $to_lines[$yi];            if (($this->ychanged[$yi] = empty($xhash[$line]))) {                continue;            }            $yhash[$line] = 1;            $this->yv[] = $line;            $this->yind[] = $yi;        }        for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {            $line = $from_lines[$xi];            if (($this->xchanged[$xi] = empty($yhash[$line]))) {                continue;            }            $this->xv[] = $line;            $this->xind[] = $xi;        }        // Find the LCS.        $this->_compareseq(0, count($this->xv), 0, count($this->yv));        // Merge edits when possible.        $this->_shiftBoundaries($from_lines, $this->xchanged, $this->ychanged);        $this->_shiftBoundaries($to_lines, $this->ychanged, $this->xchanged);        // Compute the edit operations.        $edits = array();        $xi = $yi = 0;        while ($xi < $n_from || $yi < $n_to) {            assert($yi < $n_to || $this->xchanged[$xi]);            assert($xi < $n_from || $this->ychanged[$yi]);            // Skip matching "snake".            $copy = array();            while ($xi < $n_from && $yi < $n_to                   && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {                $copy[] = $from_lines[$xi++];                ++$yi;            }            if ($copy) {                $edits[] = &new Text_Diff_Op_copy($copy);            }            // Find deletes & adds.            $delete = array();            while ($xi < $n_from && $this->xchanged[$xi]) {                $delete[] = $from_lines[$xi++];            }            $add = array();            while ($yi < $n_to && $this->ychanged[$yi]) {                $add[] = $to_lines[$yi++];            }            if ($delete && $add) {                $edits[] = &new Text_Diff_Op_change($delete, $add);            } elseif ($delete) {                $edits[] = &new Text_Diff_Op_delete($delete);            } elseif ($add) {                $edits[] = &new Text_Diff_Op_add($add);            }        }        return $edits;    }    /**     * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,     * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized     * segments.     *     * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of     * NCHUNKS+1 (X, Y) indexes giving the diving points between sub     * sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),     * the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==     * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).     *     * This function assumes that the first lines of the specified portions of     * the two files do not match, and likewise that the last lines do not     * match.  The caller must trim matching lines from the beginning and end     * of the portions it is going to specify.     */    function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks)    {        $flip = false;        if ($xlim - $xoff > $ylim - $yoff) {            /* Things seems faster (I'm not sure I understand why) when the             * shortest sequence is in X. */            $flip = true;            list ($xoff, $xlim, $yoff, $ylim)                = array($yoff, $ylim, $xoff, $xlim);        }        if ($flip) {            for ($i = $ylim - 1; $i >= $yoff; $i--) {                $ymatches[$this->xv[$i]][] = $i;            }        } else {            for ($i = $ylim - 1; $i >= $yoff; $i--) {                $ymatches[$this->yv[$i]][] = $i;            }        }        $this->lcs = 0;        $this->seq[0]= $yoff - 1;        $this->in_seq = array();        $ymids[0] = array();        $numer = $xlim - $xoff + $nchunks - 1;        $x = $xoff;        for ($chunk = 0; $chunk < $nchunks; $chunk++) {            if ($chunk > 0) {                for ($i = 0; $i <= $this->lcs; $i++) {                    $ymids[$i][$chunk - 1] = $this->seq[$i];                }            }            $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks);            for (; $x < $x1; $x++) {                $line = $flip ? $this->yv[$x] : $this->xv[$x];                if (empty($ymatches[$line])) {                    continue;                }                $matches = $ymatches[$line];                reset($matches);                while (list(, $y) = each($matches)) {                    if (empty($this->in_seq[$y])) {                        $k = $this->_lcsPos($y);                        assert($k > 0);                        $ymids[$k] = $ymids[$k - 1];                        break;                    }                }                while (list(, $y) = each($matches)) {                    if ($y > $this->seq[$k - 1]) {                        assert($y <= $this->seq[$k]);                        /* Optimization: this is a common case: next match is                         * just replacing previous match. */                        $this->in_seq[$this->seq[$k]] = false;                        $this->seq[$k] = $y;                        $this->in_seq[$y] = 1;                    } elseif (empty($this->in_seq[$y])) {                        $k = $this->_lcsPos($y);                        assert($k > 0);                        $ymids[$k] = $ymids[$k - 1];                    }                }            }        }        $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);