Merge "Enable RCFilters app on Watchlist"

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

diff --git a/includes/diff/DiffEngine.php b/includes/diff/DiffEngine.php
index 1853b86..53378e5 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;
@@ -71,11 +74,11 @@ class DiffEngine {
         *
         * @param string[] $from_lines
         * @param string[] $to_lines
+        * @throws ComplexityException
         *
         * @return DiffOp[]
         */
        public function diff( $from_lines, $to_lines ) {
-
                // Diff and store locally
                $this->diffInternal( $from_lines, $to_lines );
 
@@ -128,6 +131,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.
@@ -170,7 +181,7 @@ class DiffEngine {
                        }
 
                        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] ) {
@@ -235,7 +246,7 @@ class DiffEngine {
                                                $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;
@@ -265,6 +276,7 @@ class DiffEngine {
        /**
         * @param string[] $from
         * @param string[] $to
+        * @throws ComplexityException
         */
        protected function diffInternal( array $from, array $to ) {
                // remember initial lengths
@@ -323,6 +335,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 ) : [];