* @file
* @ingroup DifferenceEngine
*/
+use MediaWiki\Diff\ComplexityException;
/**
* This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
private $tooLong;
private $powLimit;
+ protected $bailoutComplexity = 0;
+
// State variables
private $maxDifferences;
private $lcsLengthCorrectedForHeuristic = false;
*
* @param string[] $from_lines
* @param string[] $to_lines
+ * @throws ComplexityException
*
* @return DiffOp[]
*/
return $edits;
}
+ /**
+ * Sets the complexity (in comparison operations) that can't be exceeded
+ * @param int $value
+ */
+ public function setBailoutComplexity( $value ) {
+ $this->bailoutComplexity = $value;
+ }
+
/**
* Adjust inserts/deletes of identical lines to join changes
* as much as possible.
}
while ( $i < $len && !$changed[$i] ) {
- assert( $j < $other_len && ! $other_changed[$j] );
+ assert( $j < $other_len && !$other_changed[$j] );
$i++;
$j++;
while ( $j < $other_len && $other_changed[$j] ) {
$i++;
}
- assert( $j < $other_len && ! $other_changed[$j] );
+ assert( $j < $other_len && !$other_changed[$j] );
$j++;
if ( $j < $other_len && $other_changed[$j] ) {
$corresponding = $i;
/**
* @param string[] $from
* @param string[] $to
+ * @throws ComplexityException
*/
protected function diffInternal( array $from, array $to ) {
// remember initial lengths
$this->m = count( $this->from );
$this->n = count( $this->to );
+ if ( $this->bailoutComplexity > 0 && $this->m * $this->n > $this->bailoutComplexity ) {
+ throw new ComplexityException();
+ }
+
$this->removed = $this->m > 0 ? array_fill( 0, $this->m, true ) : [];
$this->added = $this->n > 0 ? array_fill( 0, $this->n, true ) : [];