Merge "Convert Special:DeletedContributions to use OOUI."

[lhc/web/wiklou.git] / includes / diff / DiffEngine.php

diff --git a/includes/diff/DiffEngine.php b/includes/diff/DiffEngine.php
index 75e8791..babd00b 100644 (file)
--- a/includes/diff/DiffEngine.php
+++ b/includes/diff/DiffEngine.php
@@ -22,6 +22,7 @@
  * @file
  * @ingroup DifferenceEngine
  */
+use MediaWiki\Diff\ComplexityException;
 
 /**
  * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
@@ -51,6 +52,8 @@ class DiffEngine {
        private $tooLong;
        private $powLimit;
 
+       protected $bailoutComplexity = 0;
+
        // State variables
        private $maxDifferences;
        private $lcsLengthCorrectedForHeuristic = false;
@@ -67,8 +70,11 @@ class DiffEngine {
        }
 
        /**
+        * Performs diff
+        *
         * @param string[] $from_lines
         * @param string[] $to_lines
+        * @throws ComplexityException
         *
         * @return DiffOp[]
         */
@@ -126,6 +132,14 @@ class DiffEngine {
                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.
@@ -138,8 +152,12 @@ class DiffEngine {
         * to be the "change".
         *
         * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
+        *
+        * @param string[] $lines
+        * @param string[] $changed
+        * @param string[] $other_changed
         */
-       private function shiftBoundaries( $lines, &$changed, $other_changed ) {
+       private function shiftBoundaries( array $lines, array &$changed, array $other_changed ) {
                $i = 0;
                $j = 0;
 
@@ -256,7 +274,12 @@ class DiffEngine {
                }
        }
 
-       protected function diffInternal( /*array*/ $from, /*array*/ $to ) {
+       /**
+        * @param string[] $from
+        * @param string[] $to
+        * @throws ComplexityException
+        */
+       protected function diffInternal( array $from, array $to ) {
                // remember initial lengths
                $m = count( $from );
                $n = count( $to );
@@ -313,6 +336,10 @@ class DiffEngine {
                $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 ) : [];