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

This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn is based on Myers' "An O(ND) difference algorithm and its variations" (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al. More...

Public Member Functions

 __construct ( $tooLong=2000000, $powLimit=1.45)
 
 diff ( $from_lines, $to_lines)
 Performs diff.
 
 getLcsLength ()
 
 setBailoutComplexity ( $value)
 Sets the complexity (in comparison operations) that can't be exceeded.
 

Public Attributes

array $added
 
bool $heuristicUsed
 
int $length
 
array $removed
 

Protected Member Functions

 diffInternal (array $from, array $to)
 

Protected Attributes

int $bailoutComplexity = 0
 

Private Member Functions

 find_middle_snake ( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
 
 lcs_rec ( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
 
 shiftBoundaries (array $lines, array &$changed, array $other_changed)
 Adjust inserts/deletes of identical lines to join changes as much as possible.
 

Static Private Member Functions

static findMostProgress ( $M, $N, $limit, $V)
 

Private Attributes

string[] $from
 
bool $lcsLengthCorrectedForHeuristic = false
 
int $m
 
float $maxDifferences
 
int $n
 
float $powLimit
 
string[] $to
 
int $tooLong
 

Detailed Description

This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn is based on Myers' "An O(ND) difference algorithm and its variations" (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.

's "An O(NP) Sequence Comparison Algorithm").

This implementation supports an upper bound on the execution time.

Some ideas (and a bit of code) are 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

Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space

Author
Guy Van den Broeck, Geoffrey T. Dairiki, Tim Starling

Definition at line 47 of file DiffEngine.php.

Constructor & Destructor Documentation

◆ __construct()

DiffEngine::__construct (   $tooLong = 2000000,
  $powLimit = 1.45 
)
Parameters
int$tooLong
float$powLimit

Definition at line 87 of file DiffEngine.php.

References $powLimit, and $tooLong.

Member Function Documentation

◆ diff()

DiffEngine::diff (   $from_lines,
  $to_lines 
)

Performs diff.

Parameters
string[]$from_lines
string[]$to_lines
Exceptions
ComplexityException
Returns
DiffOp[]

Definition at line 101 of file DiffEngine.php.

References diffInternal(), and shiftBoundaries().

◆ diffInternal()

DiffEngine::diffInternal ( array  $from,
array  $to 
)
protected
Parameters
string[]$from
string[]$to
Exceptions
ComplexityException

Definition at line 302 of file DiffEngine.php.

References $added, $from, $m, $n, $removed, $to, lcs_rec(), n, and wfDebug().

Referenced by diff().

◆ find_middle_snake()

DiffEngine::find_middle_snake (   $bottoml1,
  $topl1,
  $bottoml2,
  $topl2,
&  $V,
&  $snake 
)
private
Parameters
int$bottoml1
int$topl1
int$bottoml2
int$topl2
array&$V
array&$snake
Returns
int

Definition at line 491 of file DiffEngine.php.

References $from, $to, findMostProgress(), and wfDebug().

Referenced by lcs_rec().

◆ findMostProgress()

static DiffEngine::findMostProgress (   $M,
  $N,
  $limit,
  $V 
)
staticprivate
Parameters
int$M
int$N
int$limit
array$V
Returns
array

Definition at line 722 of file DiffEngine.php.

Referenced by find_middle_snake().

◆ getLcsLength()

DiffEngine::getLcsLength ( )
Returns
int

Definition at line 804 of file DiffEngine.php.

References $length.

◆ lcs_rec()

DiffEngine::lcs_rec (   $bottoml1,
  $topl1,
  $bottoml2,
  $topl2,
&  $V,
&  $snake 
)
private
Parameters
int$bottoml1
int$topl1
int$bottoml2
int$topl2
array&$V
array&$snake
Returns
int

Definition at line 440 of file DiffEngine.php.

References find_middle_snake(), and lcs_rec().

Referenced by diffInternal(), and lcs_rec().

◆ setBailoutComplexity()

DiffEngine::setBailoutComplexity (   $value)

Sets the complexity (in comparison operations) that can't be exceeded.

Parameters
int$value

Definition at line 158 of file DiffEngine.php.

Referenced by Diff\__construct().

◆ shiftBoundaries()

DiffEngine::shiftBoundaries ( array  $lines,
array &  $changed,
array  $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).

Parameters
string[]$lines
string[]&$changed
string[]$other_changed

Definition at line 179 of file DiffEngine.php.

References $lines.

Referenced by diff().

Member Data Documentation

◆ $added

array DiffEngine::$added

Definition at line 79 of file DiffEngine.php.

Referenced by diffInternal().

◆ $bailoutComplexity

int DiffEngine::$bailoutComplexity = 0
protected

Definition at line 65 of file DiffEngine.php.

◆ $from

string [] DiffEngine::$from
private

Definition at line 51 of file DiffEngine.php.

Referenced by diffInternal(), and find_middle_snake().

◆ $heuristicUsed

bool DiffEngine::$heuristicUsed

Definition at line 81 of file DiffEngine.php.

◆ $lcsLengthCorrectedForHeuristic

bool DiffEngine::$lcsLengthCorrectedForHeuristic = false
private

Definition at line 71 of file DiffEngine.php.

◆ $length

int DiffEngine::$length

Definition at line 75 of file DiffEngine.php.

Referenced by getLcsLength().

◆ $m

int DiffEngine::$m
private

Definition at line 55 of file DiffEngine.php.

Referenced by diffInternal().

◆ $maxDifferences

float DiffEngine::$maxDifferences
private

Definition at line 69 of file DiffEngine.php.

◆ $n

int DiffEngine::$n
private

Definition at line 57 of file DiffEngine.php.

Referenced by diffInternal().

◆ $powLimit

float DiffEngine::$powLimit
private

Definition at line 62 of file DiffEngine.php.

Referenced by __construct().

◆ $removed

array DiffEngine::$removed

Definition at line 77 of file DiffEngine.php.

Referenced by diffInternal().

◆ $to

string [] DiffEngine::$to
private

Definition at line 53 of file DiffEngine.php.

Referenced by diffInternal(), and find_middle_snake().

◆ $tooLong

int DiffEngine::$tooLong
private

Definition at line 60 of file DiffEngine.php.

Referenced by __construct().

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