Performance improvements to diff algorithms
[lhc/web/wiklou.git] / includes / DifferenceEngine.php
index 1df4fea..d3bf205 100644 (file)
@@ -74,9 +74,10 @@ class DifferenceEngine {
        }
 
        function showDiffPage( $diffOnly = false ) {
-               global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol;
+               global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol, $wgEnableHtmlDiff;
                wfProfileIn( __METHOD__ );
 
+
                # If external diffs are enabled both globally and for the user,
                # we'll use the application/x-external-editor interface to call
                # an external diff tool like kompare, kdiff3, etc.
@@ -265,11 +266,16 @@ CONTROL;
                        '<div id="mw-diff-ntitle3">' . $newminor . $sk->revComment( $this->mNewRev, !$diffOnly, true ) . $rdel . "</div>" .
                        '<div id="mw-diff-ntitle4">' . $nextlink . $patrol . '</div>';
 
-               $this->showDiff( $oldHeader, $newHeader );
+               if($wgEnableHtmlDiff){
+                       $this->renderHtmlDiff();
+               }else{
 
-               if ( !$diffOnly )
-               $this->renderNewRevision();
+                       $this->showDiff( $oldHeader, $newHeader );
 
+                       if ( !$diffOnly ){
+                               $this->renderNewRevision();
+                       }
+               }
                wfProfileOut( __METHOD__ );
        }
 
@@ -319,6 +325,65 @@ CONTROL;
                wfProfileOut( __METHOD__ );
        }
 
+
+       function renderHtmlDiff() {
+               global $wgOut;
+               wfProfileIn( __METHOD__ );
+
+               $this->showDiffStyle();
+
+               #add deleted rev tag if needed
+               if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
+                       $wgOut->addWikiMsg( 'rev-deleted-text-permission' );
+               } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
+                       $wgOut->addWikiMsg( 'rev-deleted-text-view' );
+               }
+
+               if( !$this->mNewRev->isCurrent() ) {
+                       $oldEditSectionSetting = $wgOut->parserOptions()->setEditSection( false );
+               }
+
+               $this->loadText();
+
+               if( is_object( $this->mOldRev ) ) {
+                       $wgOut->setRevisionId( $this->mOldRev->getId() );
+               }
+
+               global $wgTitle, $wgParser, $wgTitle;
+               $popts = $wgOut->parserOptions();
+               $oldTidy = $popts->setTidy( TRUE );
+
+               $parserOutput = $wgParser->parse($this->mOldtext, $wgTitle, $popts, TRUE, TRUE, $wgOut->mRevisionId );
+               $popts->setTidy( $oldTidy );
+
+               //only for new?
+               //$wgOut->addParserOutputNoText( $parserOutput );
+               $oldHtml =      $parserOutput->getText();
+               wfRunHooks( 'OutputPageBeforeHTML',array( &$wgOut, &$oldHtml ) );
+
+               if( is_object( $this->mNewRev ) ) {
+                       $wgOut->setRevisionId( $this->mNewRev->getId() );
+               }
+
+               $popts = $wgOut->parserOptions();
+               $oldTidy = $popts->setTidy( TRUE );
+
+               $parserOutput = $wgParser->parse($this->mNewtext, $wgTitle, $popts, TRUE, TRUE, $wgOut->mRevisionId );
+               $popts->setTidy( $oldTidy );
+
+               //only for new?
+               $wgOut->addParserOutputNoText( $parserOutput );
+               $newHtml =      $parserOutput->getText();
+               wfRunHooks( 'OutputPageBeforeHTML',array( &$wgOut, &$newHtml ) );
+
+               unset($parserOutput,$popts);
+
+               $differ = new HTMLDiffer(new DelegatingContentHandler($wgOut));
+               $differ->htmlDiff($oldHtml, $newHtml);
+
+               wfProfileOut( __METHOD__ );
+       }
+
        /**
         * Show the first revision of an article. Uses normal diff headers in
         * contrast to normal "old revision" display style.
@@ -920,22 +985,71 @@ class _DiffEngine {
 
        const MAX_XREF_LENGTH =  10000;
 
-       function diff ($from_lines, $to_lines) {
+       function diff ($from_lines, $to_lines){
                wfProfileIn( __METHOD__ );
 
-               global $wgExternalDiffEngine;
+               // Diff and store locally
+               $this->diff_local($from_lines, $to_lines);
 
+               // Merge edits when possible
+               $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
+               $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
+
+               // Compute the edit operations.
                $n_from = sizeof($from_lines);
                $n_to = sizeof($to_lines);
 
+               $edits = array();
+               $xi = $yi = 0;
+               while ($xi < $n_from || $yi < $n_to) {
+                       USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
+                       USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
+
+                       // Skip matching "snake".
+                       $copy = array();
+                       while ( $xi < $n_from && $yi < $n_to
+                       && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
+                               $copy[] = $from_lines[$xi++];
+                               ++$yi;
+                       }
+                       if ($copy)
+                       $edits[] = new _DiffOp_Copy($copy);
+
+                       // Find deletes & adds.
+                       $delete = array();
+                       while ($xi < $n_from && $this->xchanged[$xi])
+                       $delete[] = $from_lines[$xi++];
+
+                       $add = array();
+                       while ($yi < $n_to && $this->ychanged[$yi])
+                       $add[] = $to_lines[$yi++];
+
+                       if ($delete && $add)
+                       $edits[] = new _DiffOp_Change($delete, $add);
+                       elseif ($delete)
+                       $edits[] = new _DiffOp_Delete($delete);
+                       elseif ($add)
+                       $edits[] = new _DiffOp_Add($add);
+               }
+               wfProfileOut( __METHOD__ );
+               return $edits;
+       }
+
+       function diff_local ($from_lines, $to_lines) {
+               global $wgExternalDiffEngine;
+               wfProfileIn( __METHOD__);
+
                if($wgExternalDiffEngine == 'wikidiff3'){
                        // wikidiff3
-                       global $IP;
-                       require_once( "$IP/includes/Diff.php" );
-                       list($this->xchanged, $this->ychanged) = wikidiff3_diff($from_lines, $to_lines, TRUE, 100000);
+                       $wikidiff3 = new WikiDiff3();
+                       $wikidiff3->diff($from_lines, $to_lines);
+                       $this->xchanged = $wikidiff3->removed;
+                       $this->ychanged = $wikidiff3->added;
+                       unset($wikidiff3);
                }else{
                        // old diff
-                       wfProfileIn( __METHOD__ ." - basicdiff");
+                       $n_from = sizeof($from_lines);
+                       $n_to = sizeof($to_lines);
                        $this->xchanged = $this->ychanged = array();
                        $this->xv = $this->yv = array();
                        $this->xind = $this->yind = array();
@@ -980,48 +1094,8 @@ class _DiffEngine {
 
                        // Find the LCS.
                        $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
-                       wfProfileOut( __METHOD__ ." - basicdiff");
-               }
-
-               // Merge edits when possible
-               $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
-               $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
-
-               // Compute the edit operations.
-               $edits = array();
-               $xi = $yi = 0;
-               while ($xi < $n_from || $yi < $n_to) {
-                       USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
-                       USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
-
-                       // Skip matching "snake".
-                       $copy = array();
-                       while ( $xi < $n_from && $yi < $n_to
-                       && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
-                               $copy[] = $from_lines[$xi++];
-                               ++$yi;
-                       }
-                       if ($copy)
-                       $edits[] = new _DiffOp_Copy($copy);
-
-                       // Find deletes & adds.
-                       $delete = array();
-                       while ($xi < $n_from && $this->xchanged[$xi])
-                       $delete[] = $from_lines[$xi++];
-
-                       $add = array();
-                       while ($yi < $n_to && $this->ychanged[$yi])
-                       $add[] = $to_lines[$yi++];
-
-                       if ($delete && $add)
-                       $edits[] = new _DiffOp_Change($delete, $add);
-                       elseif ($delete)
-                       $edits[] = new _DiffOp_Delete($delete);
-                       elseif ($add)
-                       $edits[] = new _DiffOp_Add($add);
                }
                wfProfileOut( __METHOD__ );
-               return $edits;
        }
 
        /**
@@ -1077,7 +1151,6 @@ class _DiffEngine {
                $numer = $xlim - $xoff + $nchunks - 1;
                $x = $xoff;
                for ($chunk = 0; $chunk < $nchunks; $chunk++) {
-                       wfProfileIn( __METHOD__ . "-chunk" );
                        if ($chunk > 0)
                        for ($i = 0; $i <= $this->lcs; $i++)
                        $ymids[$i][$chunk-1] = $this->seq[$i];
@@ -1130,7 +1203,6 @@ class _DiffEngine {
                if ($end == 0 || $ypos > $this->seq[$end]) {
                        $this->seq[++$this->lcs] = $ypos;
                        $this->in_seq[$ypos] = 1;
-                       wfProfileOut( __METHOD__ );
                        return $this->lcs;
                }
 
@@ -2014,4 +2086,4 @@ class TableDiffFormatter extends DiffFormatter {
                }
                wfProfileOut( __METHOD__ );
        }
-}
+}
\ No newline at end of file