MediaWiki  1.23.2
Public Member Functions | Public Attributes | Protected Attributes | Private Member Functions | List of all members
DiffEngine Class Reference
DifferenceEngine

Class used internally by Diff to actually compute the diffs. More...

Public Member Functions

 diff ( $from_lines, $to_lines)
 

Public Attributes

 $in_seq = array()
 
 $ychanged
 
 $yind = array()
 
 $yv = array()
 
const MAX_XREF_LENGTH = 10000
 

Protected Attributes

 $lcs = 0
 
 $seq = array()
 
 $xchanged
 
 $xind = array()
 
 $xv = array()
 

Private Member Functions

 compareSeq ( $xoff, $xlim, $yoff, $ylim)
 Find LCS of two sequences. More...
 
 diag ( $xoff, $xlim, $yoff, $ylim, $nchunks)
 Divide the Largest Common Subsequence (LCS) of the sequences [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally sized segments. More...
 
 diffLocal ( $from_lines, $to_lines)
 
 lcsPos ( $ypos)
 
 lineHash ( $line)
 Returns the whole line if it's small enough, or the MD5 hash otherwise. More...
 
 shiftBoundaries ( $lines, &$changed, $other_changed)
 Adjust inserts/deletes of identical lines to join changes as much as possible. More...
 

Detailed Description

Class used internally by Diff to actually compute the diffs.

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 are (and a bit of code) are from from analyze.c, from GNU diffutils-2.7, which can be found at: ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz

closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations) are my own.

Line length limits for robustness added by Tim Starling, 2005-08-31 Alternative implementation added by Guy Van den Broeck, 2008-07-30

Author
Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
Access:\n private

Definition at line 203 of file DairikiDiff.php.

Member Function Documentation

◆ compareSeq()

DiffEngine::compareSeq (   $xoff,
  $xlim,
  $yoff,
  $ylim 
)
private

Find LCS of two sequences.

The results are recorded in the vectors $this->{x,y}changed[], by storing a 1 in the element for each line that is an insertion or deletion (ie. is not in the LCS).

The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.

Note that XLIM, YLIM are exclusive bounds. All line numbers are origin-0 and discarded lines are not counted.

Parameters
int$xoff
int$xlim
int$yoff
int$ylim

Definition at line 521 of file DairikiDiff.php.

References $lcs, diag(), and list.

Referenced by diffLocal().

◆ diag()

DiffEngine::diag (   $xoff,
  $xlim,
  $yoff,
  $ylim,
  $nchunks 
)
private

Divide 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.

Parameters
int$xoff
int$xlim
int$yoff
int$ylim
int$nchunks
Returns
array List of two elements, integer and array[].

Definition at line 389 of file DairikiDiff.php.

References $lcs, $line, $matches, $n, array(), lcsPos(), and list.

Referenced by compareSeq().

◆ diff()

DiffEngine::diff (   $from_lines,
  $to_lines 
)
Parameters
string[]$from_lines
string[]$to_lines
Returns
DiffOp[]

Definition at line 221 of file DairikiDiff.php.

References array(), diffLocal(), shiftBoundaries(), wfProfileIn(), and wfProfileOut().

◆ diffLocal()

DiffEngine::diffLocal (   $from_lines,
  $to_lines 
)
private
Parameters
string[]$from_lines
string[]$to_lines

Definition at line 281 of file DairikiDiff.php.

References $line, array(), compareSeq(), global, lineHash(), wfProfileIn(), and wfProfileOut().

Referenced by diff().

◆ lcsPos()

DiffEngine::lcsPos (   $ypos)
private
Parameters
int$ypos
Returns
int

Definition at line 476 of file DairikiDiff.php.

References $lcs.

Referenced by diag().

◆ lineHash()

DiffEngine::lineHash (   $line)
private

Returns the whole line if it's small enough, or the MD5 hash otherwise.

Parameters
string$line
Returns
string

Definition at line 356 of file DairikiDiff.php.

References $line.

Referenced by diffLocal().

◆ shiftBoundaries()

DiffEngine::shiftBoundaries (   $lines,
&  $changed,
  $other_changed 
)
private

Adjust inserts/deletes of identical lines to join changes as much as possible.

We do something when a run of changed lines include a line at one end and has an excluded, identical line at the other. We are free to choose which identical line is included. ‘compareseq’ usually chooses the one at the beginning, but usually it is cleaner to consider the following identical line to be the "change".

This is extracted verbatim from analyze.c (GNU diffutils-2.7).

Definition at line 579 of file DairikiDiff.php.

References $changed, $lines, wfProfileIn(), and wfProfileOut().

Referenced by diff().

Member Data Documentation

◆ $in_seq

DiffEngine::$in_seq = array()

Definition at line 211 of file DairikiDiff.php.

◆ $lcs

DiffEngine::$lcs = 0
protected

Definition at line 213 of file DairikiDiff.php.

Referenced by compareSeq(), diag(), and lcsPos().

◆ $seq

DiffEngine::$seq = array()
protected

Definition at line 211 of file DairikiDiff.php.

◆ $xchanged

DiffEngine::$xchanged
protected

Definition at line 206 of file DairikiDiff.php.

◆ $xind

DiffEngine::$xind = array()
protected

Definition at line 209 of file DairikiDiff.php.

◆ $xv

DiffEngine::$xv = array()
protected

Definition at line 208 of file DairikiDiff.php.

◆ $ychanged

DiffEngine::$ychanged

Definition at line 206 of file DairikiDiff.php.

◆ $yind

DiffEngine::$yind = array()

Definition at line 209 of file DairikiDiff.php.

◆ $yv

DiffEngine::$yv = array()

Definition at line 208 of file DairikiDiff.php.

◆ MAX_XREF_LENGTH

const DiffEngine::MAX_XREF_LENGTH = 10000

Definition at line 204 of file DairikiDiff.php.

The documentation for this class was generated from the following file: