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

	diff_range ( $from_lines, $to_lines)

	getLcsLength ()

	setBailoutComplexity ( $value)
	Sets the complexity (in comparison operations) that can't be exceeded. More...

Public Attributes
	$added

	$heuristicUsed

	$length

	$removed

Protected Member Functions
	diffInternal (array $from, array $to)

Protected Attributes
	$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. More...

Static Private Member Functions
static	findMostProgress ( $M, $N, $limit, $V)

Private Attributes
	$from

	$lcsLengthCorrectedForHeuristic = false

	$m

	$maxDifferences

	$n

	$powLimit

	$to

	$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 44 of file DiffEngine.php.

Constructor & Destructor Documentation

◆ __construct()

DiffEngine::__construct	(	$tooLong = `2000000`,
		$powLimit = `1.45`
	)

Definition at line 67 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 81 of file DiffEngine.php.

References captcha-old\count, diffInternal(), and shiftBoundaries().

Referenced by diff_range().

◆ diff_range()

DiffEngine::diff_range	(	$from_lines,
		$to_lines
	)

Definition at line 410 of file DiffEngine.php.

References diff(), and n.

◆ diffInternal()

DiffEngine::diffInternal	(	array	$from,
		array	$to
	)

protected

Parameters

string[]	$from
string[]	$to

Exceptions

ComplexityException

Definition at line 281 of file DiffEngine.php.

References $added, $from, $m, $n, $removed, $to, as, captcha-old\count, from, lcs_rec(), n, and wfDebug().

Referenced by diff().

◆ find_middle_snake()

DiffEngine::find_middle_snake	(		$bottoml1,
			$topl1,
			$bottoml2,
			$topl2,
		&	$V,
		&	$snake
	)

private

Definition at line 489 of file DiffEngine.php.

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

Referenced by lcs_rec().

◆ findMostProgress()

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

staticprivate

Definition at line 713 of file DiffEngine.php.

Referenced by find_middle_snake().

◆ getLcsLength()

DiffEngine::getLcsLength ( )

Returns: mixed

Definition at line 795 of file DiffEngine.php.

References $length.

◆ lcs_rec()

DiffEngine::lcs_rec	(		$bottoml1,
			$topl1,
			$bottoml2,
			$topl2,
		&	$V,
		&	$snake
	)

private

Definition at line 445 of file DiffEngine.php.

References find_middle_snake().

Referenced by diffInternal().

◆ setBailoutComplexity()

DiffEngine::setBailoutComplexity ( $value )

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

Parameters

int $value

Definition at line 138 of file DiffEngine.php.

References $value.

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 159 of file DiffEngine.php.

References $lines, and captcha-old\count.

Referenced by diff().

Member Data Documentation

◆ $added

DiffEngine::$added

Definition at line 64 of file DiffEngine.php.

Referenced by diffInternal().

◆ $bailoutComplexity

DiffEngine::$bailoutComplexity = 0

protected

Definition at line 55 of file DiffEngine.php.

◆ $from

DiffEngine::$from

private

Definition at line 47 of file DiffEngine.php.

Referenced by diffInternal(), and find_middle_snake().

◆ $heuristicUsed

DiffEngine::$heuristicUsed

Definition at line 65 of file DiffEngine.php.

◆ $lcsLengthCorrectedForHeuristic

DiffEngine::$lcsLengthCorrectedForHeuristic = false

private

Definition at line 59 of file DiffEngine.php.

◆ $length

DiffEngine::$length

Definition at line 62 of file DiffEngine.php.

Referenced by getLcsLength().

◆ $m

DiffEngine::$m

private

Definition at line 49 of file DiffEngine.php.

Referenced by diffInternal().

◆ $maxDifferences

DiffEngine::$maxDifferences

private

Definition at line 58 of file DiffEngine.php.

◆ $n

DiffEngine::$n

private

Definition at line 50 of file DiffEngine.php.

Referenced by diffInternal().

◆ $powLimit

DiffEngine::$powLimit

private

Definition at line 53 of file DiffEngine.php.

Referenced by __construct().

◆ $removed

DiffEngine::$removed

Definition at line 63 of file DiffEngine.php.

Referenced by diffInternal().

◆ $to

DiffEngine::$to

private

Definition at line 48 of file DiffEngine.php.

Referenced by diffInternal(), and find_middle_snake().

◆ $tooLong

DiffEngine::$tooLong

private

Definition at line 52 of file DiffEngine.php.

Referenced by __construct().

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

includes/diff/DiffEngine.php

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ __construct()

Member Function Documentation

◆ diff()

◆ diff_range()

◆ diffInternal()

◆ find_middle_snake()

◆ findMostProgress()

◆ getLcsLength()

◆ lcs_rec()

◆ setBailoutComplexity()

◆ shiftBoundaries()

Member Data Documentation

◆ $added

◆ $bailoutComplexity

◆ $from

◆ $heuristicUsed

◆ $lcsLengthCorrectedForHeuristic

◆ $length

◆ $m

◆ $maxDifferences

◆ $n

◆ $powLimit

◆ $removed

◆ $to

◆ $tooLong