From e45cf2b88337313a9fafdad587c092d9d943a9a6 Mon Sep 17 00:00:00 2001 From: Guy Van den Broeck Date: Tue, 5 Aug 2008 19:40:29 +0000 Subject: [PATCH] Alternative experimental diff implementation. Enable by setting = 'wikidiff3'. --- includes/Diff.php | 472 ++++++++++++++++++++++++++++++++++ includes/DifferenceEngine.php | 455 ++++++++++++++++---------------- 2 files changed, 701 insertions(+), 226 deletions(-) create mode 100644 includes/Diff.php diff --git a/includes/Diff.php b/includes/Diff.php new file mode 100644 index 0000000000..4a6f117374 --- /dev/null +++ b/includes/Diff.php @@ -0,0 +1,472 @@ + + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * or see http://www.gnu.org/ + */ + +/** + * Implementation of the Diff algorithm. + * + * DO NOT USE ON PRODUCTION SYSTEMS + * + * The algorithm is based on the O(NP) LCS algorithm as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm" + * and extended with my own ideas. + * + * @return array($from_removed, $to_added) + * TRUE if the token was removed or added. + * + * @author Guy Van den Broeck + */ +function wikidiff3_diff(array $from, array $to, $boundRunningTime=FALSE, $max_NP_before_bound = 800000){ + wfProfileIn( __METHOD__ ); + + $m = sizeof($from); + $n = sizeof($to); + + $result_from = array_fill(0,$m,TRUE); + $result_to = array_fill(0,$n,TRUE); + + //reduce the complexity for the next step (intentionally done twice) + //remove common tokens at the start + $i=0; + while($i<$m && $i<$n && $from[$i]===$to[$i]){ + $result_from[$i] = $result_to[$i] = FALSE; + unset($from[$i],$to[$i]); + ++$i; + } + + //remove common tokens at the end + $j=1; + while($i+$j<=$m && $i+$j<=$n && $from[$m-$j]===$to[$n-$j]){ + $result_from[$m-$j] = $result_to[$n-$j] = FALSE; + unset($from[$m-$j],$to[$n-$j]); + ++$j; + } + + $newFrom = $newFromIndex = $newTo = $newToIndex = array(); + + //remove tokens not in both sequences + $shared = array_fill_keys($from,FALSE); + foreach($to as $index => $el){ + if(array_key_exists($el,$shared)){ + //keep it + $shared[$el] = TRUE; + $newTo[] = $el; + $newToIndex[] = $index; + } + } + foreach($from as $index => $el){ + if($shared[$el]){ + //keep it + $newFrom[] = $el; + $newFromIndex[] = $index; + } + } + + unset($from, $to, $shared); + + $m2 = sizeof($newFrom); + $n2 = sizeof($newTo); + $offsetx = $offsety = 0; + $from_inLcs = new InLcs($m2); + $to_inLcs = new InLcs($n2); + + wikidiff3_diffPart($newFrom, $newTo, $from_inLcs, $to_inLcs, $m2, $n2, $offsetx, $offsety, $m2, $boundRunningTime, $max_NP_before_bound); + + foreach($from_inLcs->inLcs as $key => $in){ + if($in){ + $result_from[$newFromIndex[$key]] = FALSE; + } + } + foreach($to_inLcs->inLcs as $key => $in){ + if($in){ + $result_to[$newToIndex[$key]] = FALSE; + } + } + + wfProfileOut( __METHOD__ ); + return array($result_from, $result_to); +} + +function wikidiff3_diffPart(array $a, array $b, InLcs $a_inLcs, InLcs $b_inLcs, $m, $n, $offsetx, $offsety, $bestKnownLcs, $boundRunningTime=FALSE, $max_NP_before_bound = 800000){ + if($bestKnownLcs==0 || $m==0 || $n==0){ + return; + } + + if($m>$n){ + return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound); + } + + $a_inLcs_sym = &$a_inLcs->inLcs; + $b_inLcs_sym = &$b_inLcs->inLcs; + + //remove common tokens at the start + while($m>0 && $n>0 && $a[0]===$b[0]){ + $a_inLcs_sym[$offsetx] = $b_inLcs_sym[$offsety] = TRUE; + ++$offsetx; ++$offsety; + --$m; --$n; + --$bestKnownLcs; + array_shift($a); + array_shift($b); + } + + //remove common tokens at the end + while($m>0 && $n>0 && $a[$m-1]===$b[$n-1]){ + $a_inLcs_sym[$offsetx+$m-1] = $b_inLcs_sym[$offsety+$n-1] = TRUE; + --$m; --$n; + --$bestKnownLcs; + array_pop($a); + array_pop($b); + } + + if($bestKnownLcs==0 || $m==0 || $n==0){ + return; + } + if($m>$n){ + return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound); + } + + $delta = $n-$m; + $delta_plus_1 = $delta+1; + $delta_min_1 = $delta-1; + + $fpForw = $snakeBeginForw = $snakeEndForw = array_fill( 0, $delta_plus_1, -1); + $lcsSizeForw = $snakekForw = $lcsSizeBack = $snakekBack = array_fill( 0, $delta_plus_1, 0); + $fpBack = $snakeBeginBack = $snakeEndBack = array_fill( 0, $delta_plus_1, $n); + $overlap = $delta>1 ? array_fill( 1, $delta_min_1, FALSE) : array(); + $bestLcsLength = $bestLcsLengthTop = $bestLcsLengthBottom = -1; + + if($boundRunningTime){ + $maxp_before_bound = max((-$delta+sqrt($delta*$delta+($max_NP_before_bound<<2)))>>1,2); + if($maxp_before_bound>=$m){ + $boundRunningTime = false; + unset($maxp_before_bound); + } + } + + $p=-1; + $m_min_1 = $m-1; + $maxp=$m_min_1-$bestLcsLength; + + while($p<$maxp){ + + if($boundRunningTime && $p>$maxp_before_bound){ + // bound the running time by stopping early + if($bestLcsLength>=0){ + // accept the best LCS thusfar + break; + }else{ + $bestLcsProgressForw = $bestkForw = 0; + foreach($lcsSizeForw as $k => $localLcsProgress){ + if($localLcsProgress>$bestLcsProgressForw || ($localLcsProgress==$bestLcsProgressForw && $bestkForw > $k)){ + $bestLcsProgressForw = $localLcsProgress; + $bestkForw = $k; + } + } + $bestLcsProgressBack = $bestkBack = 0; + foreach($lcsSizeBack as $k => $localLcsProgress){ + if($localLcsProgress>$bestLcsProgressBack || ($localLcsProgress==$bestLcsProgressBack && $bestkBack < $k)){ + $bestLcsProgressBack = $localLcsProgress; + $bestkBack = $k; + } + } + if($fpForw[$bestkForw]-$bestkForw>$fpBack[$bestkBack]-$bestkBack){ + // This is hard, maybe try some more? Can this even happen? A solution will be found soon anyway. + }else{ + // lets do this + $topSnakeStart = $snakeBeginForw[$bestkForw]; + $topSnakeEnd = $snakeEndForw[$bestkForw]; + $topSnakek = $snakekForw[$bestkForw]; + $bestLcsLengthTop = $lcsSizeForw[$bestkBack] + $topSnakeStart - $topSnakeEnd; + + $bottomSnakeStart = $snakeEndBack[$bestkBack]+1; + $bottomSnakeEnd = $snakeBeginBack[$bestkBack]+1; + $bottomSnakek = $snakekBack[$bestkBack]; + $bestLcsLengthBottom = $lcsSizeBack[$bestkBack] + $bottomSnakeStart - $bottomSnakeEnd; + + if($bottomSnakeStart-$topSnakeEnd>$n*0.6 && ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek)>$m*0.6){ + // cut the sequence from both sides (there isn't enough progress, 60% of the sequence is not covered) + // also diff the middle now + if($bottomSnakeEnd>($fpForw[$bestkForw]>>1)){ + // do the middle diff between the snakes + wfDebug(" Limiting diff run time from both sides, middle between snakes\n"); + $m_t = ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek); + $n_t = $bottomSnakeStart-$topSnakeEnd; + $a_t = array_slice($a, $topSnakeEnd-$topSnakek, $m_t); + $b_t = array_slice($b, $topSnakeEnd, $n_t); + $offsetx_t = $offsetx+($topSnakeEnd-$topSnakek); + $offsety_t = $offsety+$topSnakeEnd; + }else{ + // the snake is too early in the sequence, do the middle diff between endpoints of progress + wfDebug(" Limiting diff run time from both sides, middle between endpoints\n"); + $m_t = ($fpBack[$bestkBack]+1-$bestkBack)-($fpForw[$bestkForw]-$bestkForw); + $n_t = $fpBack[$bestkBack]+1-$fpForw[$bestkForw]; + $a_t = array_slice($a, $fpForw[$bestkForw]-$bestkForw, $m_t); + $b_t = array_slice($b, $fpForw[$bestkForw], $n_t); + $offsetx_t = $offsetx+($fpForw[$bestkForw]-$bestkForw); + $offsety_t = $offsety+$fpForw[$bestkForw]; + } + wikidiff3_diffPart($a_t, $b_t, $a_inLcs, $b_inLcs, $m_t, $n_t, $offsetx_t, $offsety_t, $m_t, $boundRunningTime, $max_NP_before_bound); + }else if(min($n-$bottomSnakeStart, $m-($bottomSnakeStart-$bottomSnakek))>min($topSnakeEnd, $topSnakeEnd-$topSnakek)){ + // the bottom snake is more interesting + wfDebug("Limiting diff run time from bottom side\n"); + $topSnakeStart = $bottomSnakeStart; + $topSnakeEnd = $bottomSnakeEnd; + $topSnakek = $bottomSnakek; + $bestLcsLengthTop = $topSnakeEnd-$topSnakek; + $bottomSnakeStart = $bottomSnakeEnd; + }else{ + // the top snake is more interesting + wfDebug(" Limiting diff run time from top side\n"); + $bottomSnakeStart = $topSnakeEnd; + $bottomSnakeEnd = $topSnakeEnd; + $bottomSnakek = $topSnakek; + $bestLcsLengthBottom = $m-($bottomSnakeEnd-$bottomSnakek); + } + break; + } + } + } + ++$p; + $overlap[-$p] = $overlap[$delta+$p] = FALSE; + + $min_p_min_1 = -$p-1; + $delta_plus_1_plus_p = $delta_plus_1+$p; + + // forward + $fpForw[$min_p_min_1] = $snakeEndForw[$min_p_min_1] = $snakekForw[$min_p_min_1] = $snakeBeginForw[$min_p_min_1] = $fpForw[$delta_plus_1_plus_p] = + $snakeBeginForw[$delta_plus_1_plus_p] = $snakeEndForw[$delta_plus_1_plus_p] = $snakekForw[$delta_plus_1_plus_p] = -1; + $lcsSizeForw[$min_p_min_1] = $lcsSizeForw[$delta_plus_1_plus_p] = 0; + + $k=-$p; + do { + $k_plus_1 = $k+1; + $k_min_1 = $k-1; + + $fpBelow = $fpForw[$k_min_1]+1; + $fpAbove = $fpForw[$k_plus_1]; + $y = &$fpForw[$k]; + if($fpBelow>$fpAbove){ + $oldy = $y = $fpBelow; + $lcsSizeForw[$k] = $lcsSizeForw[$k_min_1]; + $snakeBeginForw[$k] = $snakeBeginForw[$k_min_1]; + $snakeEndForw[$k] = $snakeEndForw[$k_min_1]; + $snakekForw[$k] = $snakekForw[$k_min_1]; + }else{ + $oldy = $y = $fpAbove; + $lcsSizeForw[$k] = $lcsSizeForw[$k_plus_1]; + $snakeBeginForw[$k] = $snakeBeginForw[$k_plus_1]; + $snakeEndForw[$k] = $snakeEndForw[$k_plus_1]; + $snakekForw[$k] = $snakekForw[$k_plus_1]; + } + $x = $y-$k; + while($x < $m && $y < $n && $a[$x]===$b[$y]){ + ++$x; + ++$y; + } + if($y-$oldy>0){ + $lcsSizeForw[$k] += $y-$oldy; + $snakeBeginForw[$k] = $oldy; + $snakeEndForw[$k]= $y; + $snakekForw[$k] = $k; + } + if($y>=$fpBack[$k] && !$overlap[$k]){ + // there is overlap + $overlap[$k]=TRUE; + $lcsLength = $lcsSizeForw[$k]+$lcsSizeBack[$k]; + if($y>$fpBack[$k]+1){ + $snakeoverlap = $y-$fpBack[$k]-1; + $lcsLength -= $snakeoverlap; + } + if($lcsLength>$bestLcsLength){ + // a better sequence found! + $bestLcsLength = $lcsLength; + + $topSnakeStart = $snakeBeginForw[$k]; + $topSnakeEnd = $snakeEndForw[$k]; + $topSnakek = $snakekForw[$k]; + + // aligned snakes bite (\ ) + // ( \ \) + $bottomSnakeStart = max($snakeEndBack[$k]+1, $topSnakeEnd+max(0,$snakekBack[$k]-$snakekForw[$k])); + $bottomSnakeEnd = max($snakeBeginBack[$k]+1, $bottomSnakeStart); + $bottomSnakek = $snakekBack[$k]; + + if($bottomSnakeEnd<$y){ + $bottomSnakeStart = $y; + $bottomSnakeEnd = $y; + $bottomSnakek = $k; + } + + $bestLcsLengthTop = $lcsSizeForw[$k]-($snakeEndForw[$k]-$snakeBeginForw[$k]); + $bestLcsLengthBottom = $lcsSizeBack[$k]-($snakeBeginBack[$k]-$snakeEndBack[$k]); + if($bestKnownLcs==$lcsLength){ + $fpForw[$k]=$y; + break 2; + } + $maxp=$m_min_1-$bestLcsLength; + } + } + if($k<$delta_min_1){ + ++$k; + }else if($k>$delta){ + --$k; + }else if($k==$delta_min_1){ + $k = $delta+$p; + }else{ + break; + } + } while(TRUE); + + // backward + $fpBack[$min_p_min_1] = $snakeBeginBack[$min_p_min_1] = $snakeEndBack[$min_p_min_1] = $snakekBack[$min_p_min_1] = + $fpBack[$delta_plus_1_plus_p] = $snakeBeginBack[$delta_plus_1_plus_p] = $snakeEndBack[$delta_plus_1_plus_p] = $snakekBack[$delta_plus_1_plus_p] = $n; + $lcsSizeBack[$min_p_min_1] = $lcsSizeBack[$delta_plus_1_plus_p] = 0; + + $k=$delta+$p; + do { + $k_plus_1 = $k+1; + $k_min_1 = $k-1; + + $fpBelow = $fpBack[$k_min_1]; + $fpAbove = $fpBack[$k_plus_1]-1; + $y = &$fpBack[$k]; + if($fpBelow<$fpAbove){ + $oldy = $y = $fpBelow; + $lcsSizeBack[$k] = $lcsSizeBack[$k_min_1]; + $snakeBeginBack[$k] = $snakeBeginBack[$k_min_1]; + $snakeEndBack[$k] = $snakeEndBack[$k_min_1]; + $snakekBack[$k] = $snakekBack[$k_min_1]; + }else{ + $oldy = $y = $fpAbove; + $lcsSizeBack[$k] = $lcsSizeBack[$k_plus_1]; + $snakeBeginBack[$k] = $snakeBeginBack[$k_plus_1]; + $snakeEndBack[$k] = $snakeEndBack[$k_plus_1]; + $snakekBack[$k] = $snakekBack[$k_plus_1]; + } + $x = $y-$k; + while($x > -1 && $y > -1 && $a[$x]===$b[$y]){ + --$x; + --$y; + } + if($oldy-$y>0){ + $lcsSizeBack[$k] += $oldy-$y; + $snakeBeginBack[$k] = $oldy; + $snakeEndBack[$k] = $y; + $snakekBack[$k] = $k; + } + if($fpForw[$k]>=$y && !$overlap[$k]){ + // there is overlap + $overlap[$k]=TRUE; + $lcsLength = $lcsSizeForw[$k]+$lcsSizeBack[$k]; + if($fpForw[$k]>$y+1){ + $snakeoverlap = $fpForw[$k]-$y-1; + $lcsLength -= $snakeoverlap; + } + if($lcsLength>$bestLcsLength){ + // a better sequence found! + $bestLcsLength = $lcsLength; + + $topSnakeStart = $snakeBeginForw[$k]; + $topSnakeEnd = $snakeEndForw[$k]; + $topSnakek = $snakekForw[$k]; + + // aligned snakes bite (\ ) + // ( \ \) + $bottomSnakeStart = max($snakeEndBack[$k]+1, $topSnakeEnd+max(0,$snakekBack[$k]-$snakekForw[$k])); + $bottomSnakeEnd = max($snakeBeginBack[$k]+1, $bottomSnakeStart); + $bottomSnakek = $snakekBack[$k]; + + if($bottomSnakeEnd<$fpForw[$k]){ + $bottomSnakeStart = $fpForw[$k]; + $bottomSnakeEnd = $fpForw[$k]; + $bottomSnakek = $k; + } + + $bestLcsLengthTop = $lcsSizeForw[$k]-($snakeEndForw[$k]-$snakeBeginForw[$k]); + $bestLcsLengthBottom = $lcsSizeBack[$k]-($snakeBeginBack[$k]-$snakeEndBack[$k]); + if($bestKnownLcs==$lcsLength){ + $fpBack[$k] = $y; + break 2; + } + $maxp=$m_min_1-$bestLcsLength; + } + } + if($k>1){ + --$k; + }else if($k<0){ + ++$k; + }else if($k==1){ + $k = -$p; + }else{ + break; + } + } while(TRUE); + } + + unset($fpForw, $fpBack, $lcsSizeForw, $lcsSizeBack); + unset($snakeBeginForw, $snakeBeginBack, $snakeEndForw, $snakeEndBack, $snakekForw, $snakekBack); + unset($overlap); + + // Mark snakes as in LCS + $maxi = $offsetx+$topSnakeEnd-$topSnakek; + for($i=$offsetx+$topSnakeStart-$topSnakek;$i<$maxi;++$i){ + $a_inLcs_sym[$i] = TRUE; + } + $maxi = $offsety+$topSnakeEnd; + for($i=$offsety+$topSnakeStart;$i<$maxi;++$i){ + $b_inLcs_sym[$i] = TRUE; + } + $maxi = $offsetx+$bottomSnakeEnd-$bottomSnakek; + for($i=$offsetx+$bottomSnakeStart-$bottomSnakek;$i<$maxi;++$i){ + $a_inLcs_sym[$i] = TRUE; + } + $maxi = $offsety+$bottomSnakeEnd; + for($i=$offsety+$bottomSnakeStart;$i<$maxi;++$i){ + $b_inLcs_sym[$i] = TRUE; + } + + $m_t = $topSnakeStart-$topSnakek; + $a_t = array_slice($a, 0, $m_t); + $b_t = array_slice($b, 0, $topSnakeStart); + + $m_b = $m-($bottomSnakeEnd-$bottomSnakek); + $n_b = $n-$bottomSnakeEnd; + $a_b = array_slice($a, $bottomSnakeEnd-$bottomSnakek, $m_b); + $b_b = array_slice($b, $bottomSnakeEnd, $n_b); + + wikidiff3_diffPart($a_t, $b_t, $a_inLcs, $b_inLcs, $m_t, $topSnakeStart, $offsetx, $offsety, $bestLcsLengthTop, $boundRunningTime, $max_NP_before_bound); + + wikidiff3_diffPart($a_b, $b_b, $a_inLcs, $b_inLcs, $m_b, $n_b, $offsetx+($bottomSnakeEnd-$bottomSnakek), $offsety+$bottomSnakeEnd, $bestLcsLengthBottom, $boundRunningTime, $max_NP_before_bound); +} + +class InLcs { + + public $inLcs; + + function __construct($length){ + $this->inLcs = $length>0 ? array_fill(0,$length,FALSE): array(); + } + + /** + * Get the length of the Longest Common Subsequence (computed) + */ + public function getLcsLength(){ + return array_sum($this->inLcs); + } + +} +?> \ No newline at end of file diff --git a/includes/DifferenceEngine.php b/includes/DifferenceEngine.php index eaa706bce5..f91d6b4409 100644 --- a/includes/DifferenceEngine.php +++ b/includes/DifferenceEngine.php @@ -3,6 +3,8 @@ * @defgroup DifferenceEngine DifferenceEngine */ +require_once( 'Diff.php' ); + /** * Constant to indicate diff cache compatibility. * Bump this when changing the diff formatting in a way that @@ -77,7 +79,7 @@ class DifferenceEngine { global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol; wfProfileIn( __METHOD__ ); - # If external diffs are enabled both globally and for the user, + # 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. if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) { @@ -88,19 +90,19 @@ class DifferenceEngine { $url2=$this->mTitle->getFullURL("action=raw&oldid=".$this->mNewid); $special=$wgLang->getNsText(NS_SPECIAL); $control=<< $this->mNewRev->getRawUserText(), 'rc_timestamp' => $db->timestamp( $this->mNewRev->getTimestamp() ), 'rc_this_oldid' => $this->mNewid, 'rc_last_oldid' => $this->mOldid, 'rc_patrolled' => 0 - ), - __METHOD__ + ), + __METHOD__ ); if( $change instanceof RecentChange ) { $rcid = $change->mAttribs['rc_id']; @@ -190,8 +192,8 @@ CONTROL; // Build the link if( $rcid ) { $patrol = ' [' . $sk->makeKnownLinkObj( - $this->mTitle, - wfMsgHtml( 'markaspatrolleddiff' ), + $this->mTitle, + wfMsgHtml( 'markaspatrolleddiff' ), "action=markpatrolled&rcid={$rcid}" ) . ']'; } else { @@ -225,33 +227,33 @@ CONTROL; if( $wgUser->isAllowed( 'deleterevision' ) ) { $revdel = SpecialPage::getTitleFor( 'Revisiondelete' ); if( !$this->mOldRev->userCan( Revision::DELETED_RESTRICTED ) ) { - // If revision was hidden from sysops + // If revision was hidden from sysops $ldel = wfMsgHtml('rev-delundel'); } else { $ldel = $sk->makeKnownLinkObj( $revdel, - wfMsgHtml('rev-delundel'), + wfMsgHtml('rev-delundel'), 'target=' . urlencode( $this->mOldRev->mTitle->getPrefixedDbkey() ) . '&oldid=' . urlencode( $this->mOldRev->getId() ) ); // Bolden oversighted content if( $this->mOldRev->isDeleted( Revision::DELETED_RESTRICTED ) ) - $ldel = "$ldel"; + $ldel = "$ldel"; } $ldel = "   ($ldel) "; // We don't currently handle well changing the top revision's settings if( $this->mNewRev->isCurrent() ) { - // If revision was hidden from sysops + // If revision was hidden from sysops $rdel = wfMsgHtml('rev-delundel'); } else if( !$this->mNewRev->userCan( Revision::DELETED_RESTRICTED ) ) { - // If revision was hidden from sysops + // If revision was hidden from sysops $rdel = wfMsgHtml('rev-delundel'); } else { $rdel = $sk->makeKnownLinkObj( $revdel, - wfMsgHtml('rev-delundel'), + wfMsgHtml('rev-delundel'), 'target=' . urlencode( $this->mNewRev->mTitle->getPrefixedDbkey() ) . '&oldid=' . urlencode( $this->mNewRev->getId() ) ); // Bolden oversighted content if( $this->mNewRev->isDeleted( Revision::DELETED_RESTRICTED ) ) - $rdel = "$rdel"; + $rdel = "$rdel"; } $rdel = "   ($rdel) "; } @@ -268,7 +270,7 @@ CONTROL; $this->showDiff( $oldHeader, $newHeader ); if ( !$diffOnly ) - $this->renderNewRevision(); + $this->renderNewRevision(); wfProfileOut( __METHOD__ ); } @@ -283,9 +285,9 @@ CONTROL; $wgOut->addHTML( "

{$this->mPagetitle}

\n" ); #add deleted rev tag if needed if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) { - $wgOut->addWikiMsg( 'rev-deleted-text-permission' ); + $wgOut->addWikiMsg( 'rev-deleted-text-permission' ); } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) { - $wgOut->addWikiMsg( 'rev-deleted-text-view' ); + $wgOut->addWikiMsg( 'rev-deleted-text-view' ); } if( !$this->mNewRev->isCurrent() ) { @@ -310,7 +312,7 @@ CONTROL; $wgOut->addHtml( "\n\n" ); } } else - $wgOut->addWikiTextTidy( $this->mNewtext ); + $wgOut->addWikiTextTidy( $this->mNewtext ); if( !$this->mNewRev->isCurrent() ) { $wgOut->parserOptions()->setEditSection( $oldEditSectionSetting ); @@ -356,9 +358,9 @@ CONTROL; $nextlink = $sk->makeKnownLinkObj( $this->mTitle, wfMsgHtml( 'nextdiff' ), 'diff=next&oldid='.$this->mNewid, '', '', 'id="differences-nextlink"' ); $header = "
{$this->mOldtitle}
" . - $sk->revUserTools( $this->mNewRev ) . "
" . - $sk->revComment( $this->mNewRev ) . "
" . - $nextlink . "
\n"; + $sk->revUserTools( $this->mNewRev ) . "
" . + $sk->revComment( $this->mNewRev ) . "
" . + $nextlink . "\n"; $wgOut->addHTML( $header ); @@ -423,9 +425,9 @@ CONTROL; wfProfileIn( __METHOD__ ); // Check if the diff should be hidden from this user if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) { - return ''; + return ''; } else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) { - return ''; + return ''; } // Cacheable? $key = false; @@ -486,7 +488,7 @@ CONTROL; dl('php_wikidiff.so'); } return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) . - $this->debug( 'wikidiff1' ); + $this->debug( 'wikidiff1' ); } if ( $wgExternalDiffEngine == 'wikidiff2' ) { @@ -505,7 +507,7 @@ CONTROL; return $text; } } - if ( $wgExternalDiffEngine !== false ) { + if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) { # Diff via the shell global $wgTmpDirectory; $tempName1 = tempnam( $wgTmpDirectory, 'diff_' ); @@ -541,9 +543,9 @@ CONTROL; $diffs = new Diff( $ota, $nta ); $formatter = new TableDiffFormatter(); return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) . - $this->debug(); + $this->debug(); } - + /** * Generate a debug comment indicating diff generating time, * server node, and generator backend. @@ -556,10 +558,10 @@ CONTROL; } $data[] = wfTimestamp( TS_DB ); return "\n"; } @@ -568,7 +570,7 @@ CONTROL; */ function localiseLineNumbers( $text ) { return preg_replace_callback( '//', - array( &$this, 'localiseLineNumbersCb' ), $text ); + array( &$this, 'localiseLineNumbersCb' ), $text ); } function localiseLineNumbersCb( $matches ) { @@ -582,7 +584,7 @@ CONTROL; */ function getMultiNotice() { if ( !is_object($this->mOldRev) || !is_object($this->mNewRev) ) - return ''; + return ''; if( !$this->mOldPage->equals( $this->mNewPage ) ) { // Comparing two different pages? Count would be meaningless. @@ -597,7 +599,7 @@ CONTROL; $n = $this->mTitle->countRevisionsBetween( $oldid, $newid ); if ( !$n ) - return ''; + return ''; return wfMsgExt( 'diff-multi', array( 'parseinline' ), $n ); } @@ -610,19 +612,19 @@ CONTROL; global $wgOut; $header = " - - - - - - - - - +
{$otitle}{$ntitle}
+ + + + + + + + "; if ( $multi != '' ) - $header .= ""; + $header .= ""; return $header . $diff . "
{$otitle}{$ntitle}
{$multi}
{$multi}
"; } @@ -657,10 +659,10 @@ CONTROL; // Load the new revision object $this->mNewRev = $this->mNewid - ? Revision::newFromId( $this->mNewid ) - : Revision::newFromTitle( $this->mTitle ); + ? Revision::newFromId( $this->mNewid ) + : Revision::newFromTitle( $this->mTitle ); if( !$this->mNewRev instanceof Revision ) - return false; + return false; // Update the new revision ID in case it was 0 (makes life easier doing UI stuff) $this->mNewid = $this->mNewRev->getId(); @@ -688,9 +690,9 @@ CONTROL; $this->mNewtitle .= " (" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . ")"; } if ( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) { - $this->mNewtitle = "{$this->mPagetitle}"; + $this->mNewtitle = "{$this->mPagetitle}"; } else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) { - $this->mNewtitle = ''.$this->mNewtitle.''; + $this->mNewtitle = ''.$this->mNewtitle.''; } // Load the old revision object @@ -722,7 +724,7 @@ CONTROL; $this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t ) ); $this->mOldtitle = "{$this->mOldPagetitle}" - . " (" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . ")"; + . " (" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . ")"; // Add an "undo" link $newUndo = $this->mNewPage->escapeLocalUrl( 'action=edit&undoafter=' . $this->mOldid . '&undo=' . $this->mNewid); if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) { @@ -730,9 +732,9 @@ CONTROL; } if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) { - $this->mOldtitle = '' . $this->mOldPagetitle . ''; + $this->mOldtitle = '' . $this->mOldPagetitle . ''; } else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) { - $this->mOldtitle = '' . $this->mOldtitle . ''; + $this->mOldtitle = '' . $this->mOldtitle . ''; } } @@ -828,7 +830,7 @@ class _DiffOp_Copy extends _DiffOp { function _DiffOp_Copy ($orig, $closing = false) { if (!is_array($closing)) - $closing = $orig; + $closing = $orig; $this->orig = $orig; $this->closing = $closing; } @@ -892,7 +894,6 @@ class _DiffOp_Change extends _DiffOp { } } - /** * Class used internally by Diff to actually compute the diffs. * @@ -911,64 +912,76 @@ class _DiffOp_Change extends _DiffOp { * are my own. * * Line length limits for robustness added by Tim Starling, 2005-08-31 + * Alternative implementation added by Guy Van den Broeck, 2008-07-30 * - * @author Geoffrey T. Dairiki, Tim Starling + * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck * @private * @ingroup DifferenceEngine */ class _DiffEngine { + const MAX_XREF_LENGTH = 10000; function diff ($from_lines, $to_lines) { wfProfileIn( __METHOD__ ); + global $wgExternalDiffEngine; + $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(); - unset($this->seq); - unset($this->in_seq); - unset($this->lcs); - - // Skip leading common lines. - for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { - if ($from_lines[$skip] !== $to_lines[$skip]) + if($wgExternalDiffEngine == 'wikidiff3'){ + // wikidiff3 + list($this->xchanged, $this->ychanged) = wikidiff3_diff($from_lines, $to_lines, TRUE, 100000); + }else{ + // old diff + wfProfileIn( __METHOD__ ." - basicdiff"); + $this->xchanged = $this->ychanged = array(); + $this->xv = $this->yv = array(); + $this->xind = $this->yind = array(); + unset($this->seq); + unset($this->in_seq); + unset($this->lcs); + + // Skip leading common lines. + for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { + if ($from_lines[$skip] !== $to_lines[$skip]) break; - $this->xchanged[$skip] = $this->ychanged[$skip] = false; - } - // Skip trailing common lines. - $xi = $n_from; $yi = $n_to; - for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { - if ($from_lines[$xi] !== $to_lines[$yi]) + $this->xchanged[$skip] = $this->ychanged[$skip] = false; + } + // Skip trailing common lines. + $xi = $n_from; $yi = $n_to; + for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { + if ($from_lines[$xi] !== $to_lines[$yi]) break; - $this->xchanged[$xi] = $this->ychanged[$yi] = false; - } + $this->xchanged[$xi] = $this->ychanged[$yi] = false; + } - // Ignore lines which do not exist in both files. - for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { - $xhash[$this->_line_hash($from_lines[$xi])] = 1; - } + // Ignore lines which do not exist in both files. + for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { + $xhash[$this->_line_hash($from_lines[$xi])] = 1; + } - for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { - $line = $to_lines[$yi]; - if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) ) + for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { + $line = $to_lines[$yi]; + if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) ) continue; - $yhash[$this->_line_hash($line)] = 1; - $this->yv[] = $line; - $this->yind[] = $yi; - } - for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { - $line = $from_lines[$xi]; - if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) ) + $yhash[$this->_line_hash($line)] = 1; + $this->yv[] = $line; + $this->yind[] = $yi; + } + for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { + $line = $from_lines[$xi]; + if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) ) continue; - $this->xv[] = $line; - $this->xind[] = $xi; - } + $this->xv[] = $line; + $this->xind[] = $xi; + } - // Find the LCS. - $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv)); + // 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); @@ -984,28 +997,28 @@ class _DiffEngine { // Skip matching "snake". $copy = array(); while ( $xi < $n_from && $yi < $n_to - && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { + && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { $copy[] = $from_lines[$xi++]; ++$yi; } if ($copy) - $edits[] = new _DiffOp_Copy($copy); + $edits[] = new _DiffOp_Copy($copy); // Find deletes & adds. $delete = array(); while ($xi < $n_from && $this->xchanged[$xi]) - $delete[] = $from_lines[$xi++]; + $delete[] = $from_lines[$xi++]; $add = array(); while ($yi < $n_to && $this->ychanged[$yi]) - $add[] = $to_lines[$yi++]; + $add[] = $to_lines[$yi++]; if ($delete && $add) - $edits[] = new _DiffOp_Change($delete, $add); + $edits[] = new _DiffOp_Change($delete, $add); elseif ($delete) - $edits[] = new _DiffOp_Delete($delete); + $edits[] = new _DiffOp_Delete($delete); elseif ($add) - $edits[] = new _DiffOp_Add($add); + $edits[] = new _DiffOp_Add($add); } wfProfileOut( __METHOD__ ); return $edits; @@ -1022,7 +1035,6 @@ class _DiffEngine { } } - /* Divide the Largest Common Subsequence (LCS) of the sequences * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally * sized segments. @@ -1040,23 +1052,22 @@ class _DiffEngine { * of the portions it is going to specify. */ function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) { - wfProfileIn( __METHOD__ ); $flip = false; if ($xlim - $xoff > $ylim - $yoff) { // Things seems faster (I'm not sure I understand why) - // when the shortest sequence in X. - $flip = true; + // when the shortest sequence in X. + $flip = true; list ($xoff, $xlim, $yoff, $ylim) = array( $yoff, $ylim, $xoff, $xlim); } if ($flip) - for ($i = $ylim - 1; $i >= $yoff; $i--) - $ymatches[$this->xv[$i]][] = $i; + for ($i = $ylim - 1; $i >= $yoff; $i--) + $ymatches[$this->xv[$i]][] = $i; else - for ($i = $ylim - 1; $i >= $yoff; $i--) - $ymatches[$this->yv[$i]][] = $i; + for ($i = $ylim - 1; $i >= $yoff; $i--) + $ymatches[$this->yv[$i]][] = $i; $this->lcs = 0; $this->seq[0]= $yoff - 1; @@ -1068,23 +1079,23 @@ class _DiffEngine { 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]; + for ($i = 0; $i <= $this->lcs; $i++) + $ymids[$i][$chunk-1] = $this->seq[$i]; $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); for ( ; $x < $x1; $x++) { $line = $flip ? $this->yv[$x] : $this->xv[$x]; - if (empty($ymatches[$line])) - continue; + if (empty($ymatches[$line])) + continue; $matches = $ymatches[$line]; reset($matches); while (list ($junk, $y) = each($matches)) - if (empty($this->in_seq[$y])) { - $k = $this->_lcs_pos($y); - USE_ASSERTS && assert($k > 0); - $ymids[$k] = $ymids[$k-1]; - break; - } + if (empty($this->in_seq[$y])) { + $k = $this->_lcs_pos($y); + USE_ASSERTS && assert($k > 0); + $ymids[$k] = $ymids[$k-1]; + break; + } while (list ( /* $junk */, $y) = each($matches)) { if ($y > $this->seq[$k-1]) { USE_ASSERTS && assert($y < $this->seq[$k]); @@ -1100,7 +1111,6 @@ class _DiffEngine { } } } - wfProfileOut( __METHOD__ . "-chunk" ); } $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); @@ -1112,13 +1122,10 @@ class _DiffEngine { } $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); - wfProfileOut( __METHOD__ ); return array($this->lcs, $seps); } function _lcs_pos ($ypos) { - wfProfileIn( __METHOD__ ); - $end = $this->lcs; if ($end == 0 || $ypos > $this->seq[$end]) { $this->seq[++$this->lcs] = $ypos; @@ -1131,9 +1138,9 @@ class _DiffEngine { while ($beg < $end) { $mid = (int)(($beg + $end) / 2); if ( $ypos > $this->seq[$mid] ) - $beg = $mid + 1; + $beg = $mid + 1; else - $end = $mid; + $end = $mid; } USE_ASSERTS && assert($ypos != $this->seq[$end]); @@ -1141,7 +1148,6 @@ class _DiffEngine { $this->in_seq[$this->seq[$end]] = false; $this->seq[$end] = $ypos; $this->in_seq[$ypos] = 1; - wfProfileOut( __METHOD__ ); return $end; } @@ -1157,24 +1163,22 @@ class _DiffEngine { * All line numbers are origin-0 and discarded lines are not counted. */ function _compareseq ($xoff, $xlim, $yoff, $ylim) { - wfProfileIn( __METHOD__ ); - // Slide down the bottom initial diagonal. while ($xoff < $xlim && $yoff < $ylim - && $this->xv[$xoff] == $this->yv[$yoff]) { + && $this->xv[$xoff] == $this->yv[$yoff]) { ++$xoff; ++$yoff; } // Slide up the top initial diagonal. while ($xlim > $xoff && $ylim > $yoff - && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { + && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { --$xlim; --$ylim; } if ($xoff == $xlim || $yoff == $ylim) - $lcs = 0; + $lcs = 0; else { // This is ad hoc but seems to work well. //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); @@ -1188,9 +1192,9 @@ class _DiffEngine { // X and Y sequences have no common subsequence: // mark all changed. while ($yoff < $ylim) - $this->ychanged[$this->yind[$yoff++]] = 1; + $this->ychanged[$this->yind[$yoff++]] = 1; while ($xoff < $xlim) - $this->xchanged[$this->xind[$xoff++]] = 1; + $this->xchanged[$this->xind[$xoff++]] = 1; } else { // Use the partitions to split this problem into subproblems. reset($seps); @@ -1200,7 +1204,6 @@ class _DiffEngine { $pt1 = $pt2; } } - wfProfileOut( __METHOD__ ); } /* Adjust inserts/deletes of identical lines to join changes @@ -1237,23 +1240,23 @@ class _DiffEngine { * $other_changed[$j] == false. */ while ($j < $other_len && $other_changed[$j]) - $j++; + $j++; while ($i < $len && ! $changed[$i]) { USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]'); $i++; $j++; while ($j < $other_len && $other_changed[$j]) - $j++; + $j++; } if ($i == $len) - break; + break; $start = $i; // Find the end of this run of changes. while (++$i < $len && $changed[$i]) - continue; + continue; do { /* @@ -1271,10 +1274,10 @@ class _DiffEngine { $changed[--$start] = 1; $changed[--$i] = false; while ($start > 0 && $changed[$start - 1]) - $start--; + $start--; USE_ASSERTS && assert('$j > 0'); while ($other_changed[--$j]) - continue; + continue; USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]'); } @@ -1296,14 +1299,14 @@ class _DiffEngine { $changed[$start++] = false; $changed[$i++] = 1; while ($i < $len && $changed[$i]) - $i++; + $i++; USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]'); $j++; if ($j < $other_len && $other_changed[$j]) { $corresponding = $i; while ($j < $other_len && $other_changed[$j]) - $j++; + $j++; } } } while ($runlength != $i - $start); @@ -1317,7 +1320,7 @@ class _DiffEngine { $changed[--$i] = 0; USE_ASSERTS && assert('$j > 0'); while ($other_changed[--$j]) - continue; + continue; USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]'); } } @@ -1376,7 +1379,7 @@ class Diff function isEmpty () { foreach ($this->edits as $edit) { if ($edit->type != 'copy') - return false; + return false; } return true; } @@ -1392,7 +1395,7 @@ class Diff $lcs = 0; foreach ($this->edits as $edit) { if ($edit->type == 'copy') - $lcs += sizeof($edit->orig); + $lcs += sizeof($edit->orig); } return $lcs; } @@ -1410,7 +1413,7 @@ class Diff foreach ($this->edits as $edit) { if ($edit->orig) - array_splice($lines, sizeof($lines), 0, $edit->orig); + array_splice($lines, sizeof($lines), 0, $edit->orig); } return $lines; } @@ -1428,7 +1431,7 @@ class Diff foreach ($this->edits as $edit) { if ($edit->closing) - array_splice($lines, sizeof($lines), 0, $edit->closing); + array_splice($lines, sizeof($lines), 0, $edit->closing); } return $lines; } @@ -1441,21 +1444,21 @@ class Diff function _check ($from_lines, $to_lines) { wfProfileIn( __METHOD__ ); if (serialize($from_lines) != serialize($this->orig())) - trigger_error("Reconstructed original doesn't match", E_USER_ERROR); + trigger_error("Reconstructed original doesn't match", E_USER_ERROR); if (serialize($to_lines) != serialize($this->closing())) - trigger_error("Reconstructed closing doesn't match", E_USER_ERROR); + trigger_error("Reconstructed closing doesn't match", E_USER_ERROR); $rev = $this->reverse(); if (serialize($to_lines) != serialize($rev->orig())) - trigger_error("Reversed original doesn't match", E_USER_ERROR); + trigger_error("Reversed original doesn't match", E_USER_ERROR); if (serialize($from_lines) != serialize($rev->closing())) - trigger_error("Reversed closing doesn't match", E_USER_ERROR); + trigger_error("Reversed closing doesn't match", E_USER_ERROR); $prevtype = 'none'; foreach ($this->edits as $edit) { if ( $prevtype == $edit->type ) - trigger_error("Edit sequence is non-optimal", E_USER_ERROR); + trigger_error("Edit sequence is non-optimal", E_USER_ERROR); $prevtype = $edit->type; } @@ -1496,7 +1499,7 @@ class MappedDiff extends Diff * have the same number of elements as $to_lines. */ function MappedDiff($from_lines, $to_lines, - $mapped_from_lines, $mapped_to_lines) { + $mapped_from_lines, $mapped_to_lines) { wfProfileIn( __METHOD__ ); assert(sizeof($from_lines) == sizeof($mapped_from_lines)); @@ -1579,8 +1582,8 @@ class DiffFormatter { $block[] = new _DiffOp_Copy($context); } $this->_block($x0, $ntrail + $xi - $x0, - $y0, $ntrail + $yi - $y0, - $block); + $y0, $ntrail + $yi - $y0, + $block); $block = false; } } @@ -1593,21 +1596,21 @@ class DiffFormatter { $y0 = $yi - sizeof($context); $block = array(); if ($context) - $block[] = new _DiffOp_Copy($context); + $block[] = new _DiffOp_Copy($context); } $block[] = $edit; } if ($edit->orig) - $xi += sizeof($edit->orig); + $xi += sizeof($edit->orig); if ($edit->closing) - $yi += sizeof($edit->closing); + $yi += sizeof($edit->closing); } if (is_array($block)) - $this->_block($x0, $xi - $x0, - $y0, $yi - $y0, - $block); + $this->_block($x0, $xi - $x0, + $y0, $yi - $y0, + $block); $end = $this->_end_diff(); wfProfileOut( __METHOD__ ); @@ -1619,15 +1622,15 @@ class DiffFormatter { $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen)); foreach ($edits as $edit) { if ($edit->type == 'copy') - $this->_context($edit->orig); + $this->_context($edit->orig); elseif ($edit->type == 'add') - $this->_added($edit->closing); + $this->_added($edit->closing); elseif ($edit->type == 'delete') - $this->_deleted($edit->orig); + $this->_deleted($edit->orig); elseif ($edit->type == 'change') - $this->_changed($edit->orig, $edit->closing); + $this->_changed($edit->orig, $edit->closing); else - trigger_error('Unknown edit type', E_USER_ERROR); + trigger_error('Unknown edit type', E_USER_ERROR); } $this->_end_block(); wfProfileOut( __METHOD__ ); @@ -1645,9 +1648,9 @@ class DiffFormatter { function _block_header($xbeg, $xlen, $ybeg, $ylen) { if ($xlen > 1) - $xbeg .= "," . ($xbeg + $xlen - 1); + $xbeg .= "," . ($xbeg + $xlen - 1); if ($ylen > 1) - $ybeg .= "," . ($ybeg + $ylen - 1); + $ybeg .= "," . ($ybeg + $ylen - 1); return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg; } @@ -1661,7 +1664,7 @@ class DiffFormatter { function _lines($lines, $prefix = ' ') { foreach ($lines as $line) - echo "$prefix $line\n"; + echo "$prefix $line\n"; } function _context($lines) { @@ -1716,40 +1719,40 @@ class ArrayDiffFormatter extends DiffFormatter { $newline = 1; $retval = array(); foreach($diff->edits as $edit) - switch($edit->type) { - case 'add': - foreach($edit->closing as $l) { - $retval[] = array( + switch($edit->type) { + case 'add': + foreach($edit->closing as $l) { + $retval[] = array( 'action' => 'add', 'new'=> $l, 'newline' => $newline++ - ); - } - break; - case 'delete': - foreach($edit->orig as $l) { - $retval[] = array( + ); + } + break; + case 'delete': + foreach($edit->orig as $l) { + $retval[] = array( 'action' => 'delete', 'old' => $l, 'oldline' => $oldline++, - ); - } - break; - case 'change': - foreach($edit->orig as $i => $l) { - $retval[] = array( + ); + } + break; + case 'change': + foreach($edit->orig as $i => $l) { + $retval[] = array( 'action' => 'change', 'old' => $l, 'new' => @$edit->closing[$i], 'oldline' => $oldline++, 'newline' => $newline++, - ); - } - break; - case 'copy': - $oldline += count($edit->orig); - $newline += count($edit->orig); - } + ); + } + break; + case 'copy': + $oldline += count($edit->orig); + $newline += count($edit->orig); + } return $retval; } } @@ -1777,13 +1780,13 @@ class _HWLDF_WordAccumulator { function _flushGroup ($new_tag) { if ($this->_group !== '') { if ($this->_tag == 'ins') - $this->_line .= '' . - htmlspecialchars ( $this->_group ) . ''; + $this->_line .= '' . + htmlspecialchars ( $this->_group ) . ''; elseif ($this->_tag == 'del') - $this->_line .= '' . - htmlspecialchars ( $this->_group ) . ''; + $this->_line .= '' . + htmlspecialchars ( $this->_group ) . ''; else - $this->_line .= htmlspecialchars ( $this->_group ); + $this->_line .= htmlspecialchars ( $this->_group ); } $this->_group = ''; $this->_tag = $new_tag; @@ -1792,21 +1795,21 @@ class _HWLDF_WordAccumulator { function _flushLine ($new_tag) { $this->_flushGroup($new_tag); if ($this->_line != '') - array_push ( $this->_lines, $this->_line ); + array_push ( $this->_lines, $this->_line ); else - # make empty lines visible by inserting an NBSP - array_push ( $this->_lines, NBSP ); + # make empty lines visible by inserting an NBSP + array_push ( $this->_lines, NBSP ); $this->_line = ''; } function addWords ($words, $tag = '') { if ($tag != $this->_tag) - $this->_flushGroup($tag); + $this->_flushGroup($tag); foreach ($words as $word) { // new-line should only come as first char of word. if ($word == '') - continue; + continue; if ($word[0] == "\n") { $this->_flushLine($tag); $word = substr($word, 1); @@ -1837,7 +1840,7 @@ class WordLevelDiff extends MappedDiff { list ($closing_words, $closing_stripped) = $this->_split($closing_lines); $this->MappedDiff($orig_words, $closing_words, - $orig_stripped, $closing_stripped); + $orig_stripped, $closing_stripped); wfProfileOut( __METHOD__ ); } @@ -1862,7 +1865,7 @@ class WordLevelDiff extends MappedDiff { } else { $m = array(); if (preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs', - $line, $m)) + $line, $m)) { $words = array_merge( $words, $m[0] ); $stripped = array_merge( $stripped, $m[1] ); @@ -1879,9 +1882,9 @@ class WordLevelDiff extends MappedDiff { foreach ($this->edits as $edit) { if ($edit->type == 'copy') - $orig->addWords($edit->orig); + $orig->addWords($edit->orig); elseif ($edit->orig) - $orig->addWords($edit->orig, 'del'); + $orig->addWords($edit->orig, 'del'); } $lines = $orig->getLines(); wfProfileOut( __METHOD__ ); @@ -1894,9 +1897,9 @@ class WordLevelDiff extends MappedDiff { foreach ($this->edits as $edit) { if ($edit->type == 'copy') - $closing->addWords($edit->closing); + $closing->addWords($edit->closing); elseif ($edit->closing) - $closing->addWords($edit->closing, 'ins'); + $closing->addWords($edit->closing, 'ins'); } $lines = $closing->getLines(); wfProfileOut( __METHOD__ ); @@ -1969,24 +1972,24 @@ class TableDiffFormatter extends DiffFormatter { function _added( $lines ) { foreach ($lines as $line) { echo '' . $this->emptyLine() . - $this->addedLine( '' . - htmlspecialchars ( $line ) . '' ) . "\n"; + $this->addedLine( '' . + htmlspecialchars ( $line ) . '' ) . "\n"; } } function _deleted($lines) { foreach ($lines as $line) { echo '' . $this->deletedLine( '' . - htmlspecialchars ( $line ) . '' ) . - $this->emptyLine() . "\n"; + htmlspecialchars ( $line ) . '' ) . + $this->emptyLine() . "\n"; } } function _context( $lines ) { foreach ($lines as $line) { echo '' . - $this->contextLine( htmlspecialchars ( $line ) ) . - $this->contextLine( htmlspecialchars ( $line ) ) . "\n"; + $this->contextLine( htmlspecialchars ( $line ) ) . + $this->contextLine( htmlspecialchars ( $line ) ) . "\n"; } } @@ -2003,11 +2006,11 @@ class TableDiffFormatter extends DiffFormatter { while ( $line = array_shift( $del ) ) { $aline = array_shift( $add ); echo '' . $this->deletedLine( $line ) . - $this->addedLine( $aline ) . "\n"; + $this->addedLine( $aline ) . "\n"; } foreach ($add as $line) { # If any leftovers echo '' . $this->emptyLine() . - $this->addedLine( $line ) . "\n"; + $this->addedLine( $line ) . "\n"; } wfProfileOut( __METHOD__ ); } -- 2.20.1