includes/diff/DifferenceEngine.php

   1 <?php
   2 /**
   3  * @defgroup DifferenceEngine DifferenceEngine
   4  */
   5
   6 /**
   7  * Constant to indicate diff cache compatibility.
   8  * Bump this when changing the diff formatting in a way that
   9  * fixes important bugs or such to force cached diff views to
  10  * clear.
  11  */
  12 define( 'MW_DIFF_VERSION', '1.11a' );
  13
  14 /**
  15  * @todo document
  16  * @ingroup DifferenceEngine
  17  */
  18 class DifferenceEngine {
  19         /**#@+
  20          * @private
  21          */
  22         var $mOldid, $mNewid, $mTitle;
  23         var $mOldtitle, $mNewtitle, $mPagetitle;
  24         var $mOldtext, $mNewtext;
  25         var $mOldPage, $mNewPage;
  26         var $mRcidMarkPatrolled;
  27         var $mOldRev, $mNewRev;
  28         var $mRevisionsLoaded = false; // Have the revisions been loaded
  29         var $mTextLoaded = 0; // How many text blobs have been loaded, 0, 1 or 2?
  30         var $mCacheHit = false; // Was the diff fetched from cache?
  31         var $htmldiff;
  32
  33         // If true, line X is not displayed when X is 1, for example to increase
  34         // readability and conserve space with many small diffs.
  35         protected $mReducedLineNumbers = false;
  36
  37         protected $unhide = false;
  38         /**#@-*/
  39
  40         /**
  41          * Constructor
  42          * @param $titleObj Title object that the diff is associated with
  43          * @param $old Integer: old ID we want to show and diff with.
  44          * @param $new String: either 'prev' or 'next'.
  45          * @param $rcid Integer: ??? FIXME (default 0)
  46          * @param $refreshCache boolean If set, refreshes the diff cache
  47          * @param $htmldiff boolean If set, output using HTMLDiff instead of raw wikicode diff
  48          * @param $unhide boolean If set, allow viewing deleted revs
  49          */
  50         function __construct( $titleObj = null, $old = 0, $new = 0, $rcid = 0,
  51                 $refreshCache = false, $htmldiff = false, $unhide = false )
  52         {
  53                 if ( $titleObj ) {
  54                         $this->mTitle = $titleObj;
  55                 } else {
  56                         global $wgTitle;
  57                         $this->mTitle = $wgTitle;
  58                 }
  59                 wfDebug("DifferenceEngine old '$old' new '$new' rcid '$rcid'\n");
  60
  61                 if ( 'prev' === $new ) {
  62                         # Show diff between revision $old and the previous one.
  63                         # Get previous one from DB.
  64                         $this->mNewid = intval($old);
  65                         $this->mOldid = $this->mTitle->getPreviousRevisionID( $this->mNewid );
  66                 } elseif ( 'next' === $new ) {
  67                         # Show diff between revision $old and the next one.
  68                         # Get next one from DB.
  69                         $this->mOldid = intval($old);
  70                         $this->mNewid = $this->mTitle->getNextRevisionID( $this->mOldid );
  71                         if ( false === $this->mNewid ) {
  72                                 # if no result, NewId points to the newest old revision. The only newer
  73                                 # revision is cur, which is "0".
  74                                 $this->mNewid = 0;
  75                         }
  76                 } else {
  77                         $this->mOldid = intval($old);
  78                         $this->mNewid = intval($new);
  79                         wfRunHooks( 'NewDifferenceEngine', array(&$titleObj, &$this->mOldid, &$this->mNewid, $old, $new) );
  80                 }
  81                 $this->mRcidMarkPatrolled = intval($rcid);  # force it to be an integer
  82                 $this->mRefreshCache = $refreshCache;
  83                 $this->htmldiff = $htmldiff;
  84                 $this->unhide = $unhide;
  85         }
  86
  87         function setReducedLineNumbers( $value = true ) {
  88                 $this->mReducedLineNumbers = $value;
  89         }
  90
  91         function getTitle() {
  92                 return $this->mTitle;
  93         }
  94
  95         function wasCacheHit() {
  96                 return $this->mCacheHit;
  97         }
  98
  99         function getOldid() {
 100                 return $this->mOldid;
 101         }
 102
 103         function getNewid() {
 104                 return $this->mNewid;
 105         }
 106
 107         function showDiffPage( $diffOnly = false ) {
 108                 global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol, $wgEnableHtmlDiff;
 109                 wfProfileIn( __METHOD__ );
 110
 111
 112                 # If external diffs are enabled both globally and for the user,
 113                 # we'll use the application/x-external-editor interface to call
 114                 # an external diff tool like kompare, kdiff3, etc.
 115                 if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) {
 116                         global $wgInputEncoding,$wgServer,$wgScript,$wgLang;
 117                         $wgOut->disable();
 118                         header ( "Content-type: application/x-external-editor; charset=".$wgInputEncoding );
 119                         $url1=$this->mTitle->getFullURL( array(
 120                                 'action' => 'raw',
 121                                 'oldid' => $this->mOldid
 122                         ) );
 123                         $url2=$this->mTitle->getFullURL( array(
 124                                 'action' => 'raw',
 125                                 'oldid' => $this->mNewid
 126                         ) );
 127                         $special=$wgLang->getNsText(NS_SPECIAL);
 128                         $control=<<<CONTROL
 129                         [Process]
 130                         Type=Diff text
 131                         Engine=MediaWiki
 132                         Script={$wgServer}{$wgScript}
 133                         Special namespace={$special}
 134
 135                         [File]
 136                         Extension=wiki
 137                         URL=$url1
 138
 139                         [File 2]
 140                         Extension=wiki
 141                         URL=$url2
 142 CONTROL;
 143                         echo($control);
 144                         return;
 145                 }
 146
 147                 $wgOut->setArticleFlag( false );
 148                 if ( !$this->loadRevisionData() ) {
 149                         $t = $this->mTitle->getPrefixedText();
 150                         $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
 151                         $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
 152                         $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
 153                         wfProfileOut( __METHOD__ );
 154                         return;
 155                 }
 156
 157                 wfRunHooks( 'DiffViewHeader', array( $this, $this->mOldRev, $this->mNewRev ) );
 158
 159                 if ( $this->mNewRev->isCurrent() ) {
 160                         $wgOut->setArticleFlag( true );
 161                 }
 162
 163                 # mOldid is false if the difference engine is called with a "vague" query for
 164                 # a diff between a version V and its previous version V' AND the version V
 165                 # is the first version of that article. In that case, V' does not exist.
 166                 if ( $this->mOldid === false ) {
 167                         $this->showFirstRevision();
 168                         $this->renderNewRevision();  // should we respect $diffOnly here or not?
 169                         wfProfileOut( __METHOD__ );
 170                         return;
 171                 }
 172
 173                 $wgOut->suppressQuickbar();
 174
 175                 $oldTitle = $this->mOldPage->getPrefixedText();
 176                 $newTitle = $this->mNewPage->getPrefixedText();
 177                 if( $oldTitle == $newTitle ) {
 178                         $wgOut->setPageTitle( $newTitle );
 179                 } else {
 180                         $wgOut->setPageTitle( $oldTitle . ', ' . $newTitle );
 181                 }
 182                 $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
 183                 $wgOut->setRobotPolicy( 'noindex,nofollow' );
 184
 185                 if ( !$this->mOldPage->userCanRead() || !$this->mNewPage->userCanRead() ) {
 186                         $wgOut->loginToUse();
 187                         $wgOut->output();
 188                         $wgOut->disable();
 189                         wfProfileOut( __METHOD__ );
 190                         return;
 191                 }
 192
 193                 $sk = $wgUser->getSkin();
 194
 195                 // Check if page is editable
 196                 $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
 197                 if ( $editable && $this->mNewRev->isCurrent() && $wgUser->isAllowed( 'rollback' ) ) {
 198                         $rollback = '&nbsp;&nbsp;&nbsp;' . $sk->generateRollback( $this->mNewRev );
 199                 } else {
 200                         $rollback = '';
 201                 }
 202
 203                 // Prepare a change patrol link, if applicable
 204                 if( $wgUseRCPatrol && $this->mTitle->userCan('patrol') ) {
 205                         // If we've been given an explicit change identifier, use it; saves time
 206                         if( $this->mRcidMarkPatrolled ) {
 207                                 $rcid = $this->mRcidMarkPatrolled;
 208                                 $rc = RecentChange::newFromId( $rcid );
 209                                 // Already patrolled?
 210                                 $rcid = is_object($rc) && !$rc->getAttribute('rc_patrolled') ? $rcid : 0;
 211                         } else {
 212                                 // Look for an unpatrolled change corresponding to this diff
 213                                 $db = wfGetDB( DB_SLAVE );
 214                                 $change = RecentChange::newFromConds(
 215                                         array(
 216                                         // Redundant user,timestamp condition so we can use the existing index
 217                                                 'rc_user_text'  => $this->mNewRev->getRawUserText(),
 218                                                 'rc_timestamp'  => $db->timestamp( $this->mNewRev->getTimestamp() ),
 219                                                 'rc_this_oldid' => $this->mNewid,
 220                                                 'rc_last_oldid' => $this->mOldid,
 221                                                 'rc_patrolled'  => 0
 222                                         ),
 223                                         __METHOD__
 224                                 );
 225                                 if( $change instanceof RecentChange ) {
 226                                         $rcid = $change->mAttribs['rc_id'];
 227                                         $this->mRcidMarkPatrolled = $rcid;
 228                                 } else {
 229                                         // None found
 230                                         $rcid = 0;
 231                                 }
 232                         }
 233                         // Build the link
 234                         if( $rcid ) {
 235                                 $patrol = ' <span class="patrollink">[' . $sk->link(
 236                                         $this->mTitle,
 237                                         wfMsgHtml( 'markaspatrolleddiff' ),
 238                                         array(),
 239                                         array(
 240                                                 'action' => 'markpatrolled',
 241                                                 'rcid' => $rcid
 242                                         ),
 243                                         array(
 244                                                 'known',
 245                                                 'noclasses'
 246                                         )
 247                                 ) . ']</span>';
 248                         } else {
 249                                 $patrol = '';
 250                         }
 251                 } else {
 252                         $patrol = '';
 253                 }
 254
 255                 # Carry over 'diffonly' param via navigation links
 256                 if( $diffOnly != $wgUser->getBoolOption('diffonly') ) {
 257                         $query['diffonly'] = $diffOnly;
 258                 }
 259
 260                 $htmldiffarg = $this->htmlDiffArgument();
 261
 262                 if( $htmldiffarg ) {
 263                         $query['htmldiff'] = $htmldiffarg['htmldiff'];
 264                 }
 265
 266                 # Make "previous revision link"
 267                 $query['diff'] = 'prev';
 268                 $query['oldid'] = $this->mOldid;
 269
 270                 $prevlink = $sk->link(
 271                         $this->mTitle,
 272                         wfMsgHtml( 'previousdiff' ),
 273                         array(
 274                                 'id' => 'differences-prevlink'
 275                         ),
 276                         $query,
 277                         array(
 278                                 'known',
 279                                 'noclasses'
 280                         )
 281                 );
 282                 # Make "next revision link"
 283                 $query['diff'] = 'next';
 284                 $query['oldid'] = $this->mNewid;
 285
 286                 if( $this->mNewRev->isCurrent() ) {
 287                         $nextlink = '&nbsp;';
 288                 } else {
 289                         $nextlink = $sk->link(
 290                                 $this->mTitle,
 291                                 wfMsgHtml( 'nextdiff' ),
 292                                 array(
 293                                         'id' => 'differences-nextlink'
 294                                 ),
 295                                 $query,
 296                                 array(
 297                                         'known',
 298                                         'noclasses'
 299                                 )
 300                         );
 301                 }
 302
 303                 $oldminor = '';
 304                 $newminor = '';
 305
 306                 if( $this->mOldRev->isMinor() ) {
 307                         $oldminor = Xml::element( 'abbr', array( 'class' => 'minor' ), wfMsg( 'minoreditletter') ) . ' ';
 308                 }
 309                 if( $this->mNewRev->isMinor() ) {
 310                         $newminor = Xml::element( 'abbr', array( 'class' => 'minor' ), wfMsg( 'minoreditletter') ) . ' ';
 311                 }
 312
 313                 $rdel = ''; $ldel = '';
 314                 if( $wgUser->isAllowed( 'deleterevision' ) ) {
 315                         if( !$this->mOldRev->userCan( Revision::DELETED_RESTRICTED ) ) {
 316                                 // If revision was hidden from sysops
 317                                 $ldel = Xml::tags( 'span', array( 'class' => 'mw-revdelundel-link' ), '(' . wfMsgHtml( 'rev-delundel' ) . ')' );
 318                         } else {
 319                                 $query = array(
 320                                         'type' => 'revision',
 321                                         'target' => $this->mOldRev->mTitle->getPrefixedDbkey(),
 322                                         'ids' => $this->mOldRev->getId()
 323                                 );
 324                                 $ldel = $sk->revDeleteLink( $query, $this->mOldRev->isDeleted( Revision::DELETED_RESTRICTED ) );
 325                         }
 326                         $ldel = "&nbsp;&nbsp;&nbsp;$ldel ";
 327                         if( !$this->mNewRev->userCan( Revision::DELETED_RESTRICTED ) ) {
 328                                 // If revision was hidden from sysops
 329                                 $rdel = Xml::tags( 'span', array( 'class'=>'mw-revdelundel-link' ), '('.wfMsgHtml( 'rev-delundel' ).')' );
 330                         } else {
 331                                 $query = array(
 332                                         'type' => 'revision',
 333                                         'target' =>  $this->mNewRev->mTitle->getPrefixedDbkey(),
 334                                         'ids' => $this->mNewRev->getId()
 335                                 );
 336                                 $rdel = $sk->revDeleteLink( $query, $this->mNewRev->isDeleted( Revision::DELETED_RESTRICTED ) );
 337                         }
 338                         $rdel = "&nbsp;&nbsp;&nbsp;$rdel ";
 339                 }
 340
 341                 $oldHeader = '<div id="mw-diff-otitle1"><strong>'.$this->mOldtitle.'</strong></div>' .
 342                         '<div id="mw-diff-otitle2">' . $sk->revUserTools( $this->mOldRev, !$this->unhide ) . "</div>" .
 343                         '<div id="mw-diff-otitle3">' . $oldminor . $sk->revComment( $this->mOldRev, !$diffOnly, !$this->unhide ).$ldel."</div>" .
 344                         '<div id="mw-diff-otitle4">' . $prevlink .'</div>';
 345                 $newHeader = '<div id="mw-diff-ntitle1"><strong>'.$this->mNewtitle.'</strong></div>' .
 346                         '<div id="mw-diff-ntitle2">' . $sk->revUserTools( $this->mNewRev, !$this->unhide ) . " $rollback</div>" .
 347                         '<div id="mw-diff-ntitle3">' . $newminor . $sk->revComment( $this->mNewRev, !$diffOnly, !$this->unhide ).$rdel."</div>" .
 348                         '<div id="mw-diff-ntitle4">' . $nextlink . $patrol . '</div>';
 349
 350                 # Check if this user can see the revisions
 351                 $allowed = $this->mOldRev->userCan(Revision::DELETED_TEXT)
 352                         && $this->mNewRev->userCan(Revision::DELETED_TEXT);
 353                 $deleted = $this->mOldRev->isDeleted(Revision::DELETED_TEXT)
 354                         || $this->mNewRev->isDeleted(Revision::DELETED_TEXT);
 355                 # Output the diff if allowed...
 356                 if( $deleted && (!$this->unhide || !$allowed) ) {
 357                         $this->showDiffStyle();
 358                         $multi = $this->getMultiNotice();
 359                         $wgOut->addHTML( $this->addHeader( '', $oldHeader, $newHeader, $multi ) );
 360                         if( !$allowed ) {
 361                                 # Give explanation for why revision is not visible
 362                                 $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n",
 363                                         array( 'rev-deleted-no-diff' ) );
 364                         } else {
 365                                 # Give explanation and add a link to view the diff...
 366                                 $link = $this->mTitle->getFullUrl( array(
 367                                         'diff' => $this->mNewid,
 368                                         'oldid' => $this->mOldid,
 369                                         'unhide' => 1
 370                                 ) );
 371                                 $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n",
 372                                         array( 'rev-deleted-unhide-diff', $link ) );
 373                         }
 374                 } else if( $wgEnableHtmlDiff && $this->htmldiff ) {
 375                         $multi = $this->getMultiNotice();
 376                         $wgOut->addHTML( '<div class="diff-switchtype">' . $sk->link(
 377                                 $this->mTitle,
 378                                 wfMsgHtml( 'wikicodecomparison' ),
 379                                 array(
 380                                         'id' => 'differences-switchtype'
 381                                 ),
 382                                 array(
 383                                         'diff' => $this->mNewid,
 384                                         'oldid' => $this->mOldid,
 385                                         'htmldiff' => 0
 386                                 ),
 387                                 array(
 388                                         'known',
 389                                         'noclasses'
 390                                 )
 391                         ) . '</div>');
 392                         $wgOut->addHTML( $this->addHeader( '', $oldHeader, $newHeader, $multi ) );
 393                         $this->renderHtmlDiff();
 394                 } else {
 395                         if( $wgEnableHtmlDiff ) {
 396                                 $wgOut->addHTML( '<div class="diff-switchtype">' . $sk->link(
 397                                         $this->mTitle,
 398                                         wfMsgHtml( 'visualcomparison' ),
 399                                         array(
 400                                                 'id' => 'differences-switchtype'
 401                                         ),
 402                                         array(
 403                                                 'diff' => $this->mNewid,
 404                                                 'oldid' => $this->mOldid,
 405                                                 'htmldiff' => 1
 406                                         ),
 407                                         array(
 408                                                 'known',
 409                                                 'noclasses'
 410                                         )
 411                                 ) . '</div>');
 412                         }
 413                         $this->showDiff( $oldHeader, $newHeader );
 414                         if( !$diffOnly ) {
 415                                 $this->renderNewRevision();
 416                         }
 417                 }
 418                 wfProfileOut( __METHOD__ );
 419         }
 420
 421         /**
 422          * Show the new revision of the page.
 423          */
 424         function renderNewRevision() {
 425                 global $wgOut, $wgUser;
 426                 wfProfileIn( __METHOD__ );
 427
 428                 $wgOut->addHTML( "<hr /><h2>{$this->mPagetitle}</h2>\n" );
 429                 # Add deleted rev tag if needed
 430                 if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 431                         $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n", 'rev-deleted-text-permission' );
 432                 } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
 433                         $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n", 'rev-deleted-text-view' );
 434                 }
 435
 436                 if( !$this->mNewRev->isCurrent() ) {
 437                         $oldEditSectionSetting = $wgOut->parserOptions()->setEditSection( false );
 438                 }
 439
 440                 $this->loadNewText();
 441                 if( is_object( $this->mNewRev ) ) {
 442                         $wgOut->setRevisionId( $this->mNewRev->getId() );
 443                 }
 444
 445                 if( $this->mTitle->isCssJsSubpage() || $this->mTitle->isCssOrJsPage() ) {
 446                         // Stolen from Article::view --AG 2007-10-11
 447                         // Give hooks a chance to customise the output
 448                         if( wfRunHooks( 'ShowRawCssJs', array( $this->mNewtext, $this->mTitle, $wgOut ) ) ) {
 449                                 // Wrap the whole lot in a <pre> and don't parse
 450                                 $m = array();
 451                                 preg_match( '!\.(css|js)$!u', $this->mTitle->getText(), $m );
 452                                 $wgOut->addHTML( "<pre class=\"mw-code mw-{$m[1]}\" dir=\"ltr\">\n" );
 453                                 $wgOut->addHTML( htmlspecialchars( $this->mNewtext ) );
 454                                 $wgOut->addHTML( "\n</pre>\n" );
 455                         }
 456                 } else {
 457                         $wgOut->addWikiTextTidy( $this->mNewtext );
 458                 }
 459
 460                 if( is_object( $this->mNewRev ) && !$this->mNewRev->isCurrent() ) {
 461                         $wgOut->parserOptions()->setEditSection( $oldEditSectionSetting );
 462                 }
 463                 # Add redundant patrol link on bottom...
 464                 if( $this->mRcidMarkPatrolled && $this->mTitle->quickUserCan('patrol') ) {
 465                         $sk = $wgUser->getSkin();
 466                         $wgOut->addHTML(
 467                                 "<div class='patrollink'>[" . $sk->link(
 468                                         $this->mTitle,
 469                                         wfMsgHtml( 'markaspatrolleddiff' ),
 470                                         array(),
 471                                         array(
 472                                                 'action' => 'markpatrolled',
 473                                                 'rcid' => $this->mRcidMarkPatrolled
 474                                         )
 475                                 ) . ']</div>'
 476                          );
 477                 }
 478
 479                 wfProfileOut( __METHOD__ );
 480         }
 481
 482
 483         function renderHtmlDiff() {
 484                 global $wgOut, $wgParser, $wgDebugComments;
 485                 wfProfileIn( __METHOD__ );
 486
 487                 $this->showDiffStyle();
 488
 489                 $wgOut->addHTML( '<h2>'.wfMsgHtml( 'visual-comparison' )."</h2>\n" );
 490                 #add deleted rev tag if needed
 491                 if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 492                         $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n", 'rev-deleted-text-permission' );
 493                 } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
 494                         $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1</div>\n", 'rev-deleted-text-view' );
 495                 }
 496
 497                 if( !$this->mNewRev->isCurrent() ) {
 498                         $oldEditSectionSetting = $wgOut->parserOptions()->setEditSection( false );
 499                 }
 500
 501                 $this->loadText();
 502
 503                 // Old revision
 504                 if( is_object( $this->mOldRev ) ) {
 505                         $wgOut->setRevisionId( $this->mOldRev->getId() );
 506                 }
 507
 508                 $popts = $wgOut->parserOptions();
 509                 $oldTidy = $popts->setTidy( true );
 510                 $popts->setEditSection( false );
 511
 512                 $parserOutput = $wgParser->parse( $this->mOldtext, $this->getTitle(), $popts, true, true, $wgOut->getRevisionId() );
 513                 $popts->setTidy( $oldTidy );
 514
 515                 //only for new?
 516                 //$wgOut->addParserOutputNoText( $parserOutput );
 517                 $oldHtml = $parserOutput->getText();
 518                 wfRunHooks( 'OutputPageBeforeHTML', array( &$wgOut, &$oldHtml ) );
 519
 520                 // New revision
 521                 if( is_object( $this->mNewRev ) ) {
 522                         $wgOut->setRevisionId( $this->mNewRev->getId() );
 523                 }
 524
 525                 $popts = $wgOut->parserOptions();
 526                 $oldTidy = $popts->setTidy( true );
 527
 528                 $parserOutput = $wgParser->parse( $this->mNewtext, $this->getTitle(), $popts, true, true, $wgOut->getRevisionId() );
 529                 $popts->setTidy( $oldTidy );
 530
 531                 $wgOut->addParserOutputNoText( $parserOutput );
 532                 $newHtml = $parserOutput->getText();
 533                 wfRunHooks( 'OutputPageBeforeHTML', array( &$wgOut, &$newHtml ) );
 534
 535                 unset($parserOutput, $popts);
 536
 537                 $differ = new HTMLDiffer(new DelegatingContentHandler($wgOut));
 538                 $differ->htmlDiff($oldHtml, $newHtml);
 539                 if ( $wgDebugComments ) {
 540                         $wgOut->addHTML( "\n<!-- HtmlDiff Debug Output:\n" . HTMLDiffer::getDebugOutput() . " End Debug -->" );
 541                 }
 542
 543                 wfProfileOut( __METHOD__ );
 544         }
 545
 546         /**
 547          * Show the first revision of an article. Uses normal diff headers in
 548          * contrast to normal "old revision" display style.
 549          */
 550         function showFirstRevision() {
 551                 global $wgOut, $wgUser;
 552                 wfProfileIn( __METHOD__ );
 553
 554                 # Get article text from the DB
 555                 #
 556                 if ( ! $this->loadNewText() ) {
 557                         $t = $this->mTitle->getPrefixedText();
 558                         $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
 559                         $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
 560                         $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
 561                         wfProfileOut( __METHOD__ );
 562                         return;
 563                 }
 564                 if ( $this->mNewRev->isCurrent() ) {
 565                         $wgOut->setArticleFlag( true );
 566                 }
 567
 568                 # Check if user is allowed to look at this page. If not, bail out.
 569                 #
 570                 if ( !$this->mTitle->userCanRead() ) {
 571                         $wgOut->loginToUse();
 572                         $wgOut->output();
 573                         wfProfileOut( __METHOD__ );
 574                         throw new MWException("Permission Error: you do not have access to view this page");
 575                 }
 576
 577                 # Prepare the header box
 578                 #
 579                 $sk = $wgUser->getSkin();
 580
 581                 $next = $this->mTitle->getNextRevisionID( $this->mNewid );
 582                 if( !$next ) {
 583                         $nextlink = '';
 584                 } else {
 585                         $nextlink = '<br/>' . $sk->link(
 586                                 $this->mTitle,
 587                                 wfMsgHtml( 'nextdiff' ),
 588                                 array(
 589                                         'id' => 'differences-nextlink'
 590                                 ),
 591                                 array(
 592                                         'diff' => 'next',
 593                                         'oldid' => $this->mNewid,
 594                                         $this->htmlDiffArgument()
 595                                 ),
 596                                 array(
 597                                         'known',
 598                                         'noclasses'
 599                                 )
 600                         );
 601                 }
 602                 $header = "<div class=\"firstrevisionheader\" style=\"text-align: center\">" .
 603                         $sk->revUserTools( $this->mNewRev ) . "<br/>" . $sk->revComment( $this->mNewRev ) . $nextlink . "</div>\n";
 604
 605                 $wgOut->addHTML( $header );
 606
 607                 $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
 608                 $wgOut->setRobotPolicy( 'noindex,nofollow' );
 609
 610                 wfProfileOut( __METHOD__ );
 611         }
 612
 613         function htmlDiffArgument(){
 614                 global $wgEnableHtmlDiff;
 615                 if($wgEnableHtmlDiff){
 616                         if($this->htmldiff){
 617                                 return array( 'htmldiff' => 1 );
 618                         }else{
 619                                 return array( 'htmldiff' => 0 );
 620                         }
 621                 }else{
 622                         return array();
 623                 }
 624         }
 625
 626         /**
 627          * Get the diff text, send it to $wgOut
 628          * Returns false if the diff could not be generated, otherwise returns true
 629          */
 630         function showDiff( $otitle, $ntitle ) {
 631                 global $wgOut;
 632                 $diff = $this->getDiff( $otitle, $ntitle );
 633                 if ( $diff === false ) {
 634                         $wgOut->addWikiMsg( 'missing-article', "<nowiki>(fixme, bug)</nowiki>", '' );
 635                         return false;
 636                 } else {
 637                         $this->showDiffStyle();
 638                         $wgOut->addHTML( $diff );
 639                         return true;
 640                 }
 641         }
 642
 643         /**
 644          * Add style sheets and supporting JS for diff display.
 645          */
 646         function showDiffStyle() {
 647                 global $wgStylePath, $wgStyleVersion, $wgOut;
 648
 649                 static $styleDone = false;
 650                 if ( $styleDone === $wgOut ) return;
 651
 652                 $wgOut->addStyle( 'common/diff.css' );
 653
 654                 // JS is needed to detect old versions of Mozilla to work around an annoyance bug.
 655                 $wgOut->addScript( "<script type=\"text/javascript\" src=\"$wgStylePath/common/diff.js?$wgStyleVersion\"></script>" );
 656
 657                 $styleDone = $wgOut;
 658         }
 659
 660         /**
 661          * Get complete diff table, including header
 662          *
 663          * @param Title $otitle Old title
 664          * @param Title $ntitle New title
 665          * @return mixed
 666          */
 667         function getDiff( $otitle, $ntitle ) {
 668                 $body = $this->getDiffBody();
 669                 if ( $body === false ) {
 670                         return false;
 671                 } else {
 672                         $multi = $this->getMultiNotice();
 673                         return $this->addHeader( $body, $otitle, $ntitle, $multi );
 674                 }
 675         }
 676
 677         /**
 678          * Get the diff table body, without header
 679          *
 680          * @return mixed
 681          */
 682         function getDiffBody() {
 683                 global $wgMemc;
 684                 wfProfileIn( __METHOD__ );
 685                 $this->mCacheHit = true;
 686                 // Check if the diff should be hidden from this user
 687                 if ( !$this->loadRevisionData() )
 688                         return '';
 689                 if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) {
 690                         return '';
 691                 } else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 692                         return '';
 693                 } else if ( $this->mOldRev && $this->mNewRev && $this->mOldRev->getID() == $this->mNewRev->getID() ) {
 694                         return '';
 695                 }
 696                 // Cacheable?
 697                 $key = false;
 698                 if ( $this->mOldid && $this->mNewid ) {
 699                         $key = wfMemcKey( 'diff', 'version', MW_DIFF_VERSION, 'oldid', $this->mOldid, 'newid', $this->mNewid );
 700                         // Try cache
 701                         if ( !$this->mRefreshCache ) {
 702                                 $difftext = $wgMemc->get( $key );
 703                                 if ( $difftext ) {
 704                                         wfIncrStats( 'diff_cache_hit' );
 705                                         $difftext = $this->localiseLineNumbers( $difftext );
 706                                         $difftext .= "\n<!-- diff cache key $key -->\n";
 707                                         wfProfileOut( __METHOD__ );
 708                                         return $difftext;
 709                                 }
 710                         } // don't try to load but save the result
 711                 }
 712                 $this->mCacheHit = false;
 713
 714                 // Loadtext is permission safe, this just clears out the diff
 715                 if ( !$this->loadText() ) {
 716                         wfProfileOut( __METHOD__ );
 717                         return false;
 718                 }
 719
 720                 $difftext = $this->generateDiffBody( $this->mOldtext, $this->mNewtext );
 721
 722                 // Save to cache for 7 days
 723                 if ( !wfRunHooks( 'AbortDiffCache', array( &$this ) ) ) {
 724                         wfIncrStats( 'diff_uncacheable' );
 725                 } else if ( $key !== false && $difftext !== false ) {
 726                         wfIncrStats( 'diff_cache_miss' );
 727                         $wgMemc->set( $key, $difftext, 7*86400 );
 728                 } else {
 729                         wfIncrStats( 'diff_uncacheable' );
 730                 }
 731                 // Replace line numbers with the text in the user's language
 732                 if ( $difftext !== false ) {
 733                         $difftext = $this->localiseLineNumbers( $difftext );
 734                 }
 735                 wfProfileOut( __METHOD__ );
 736                 return $difftext;
 737         }
 738
 739         /**
 740          * Make sure the proper modules are loaded before we try to
 741          * make the diff
 742          */
 743         private function initDiffEngines() {
 744                 global $wgExternalDiffEngine;
 745                 if ( $wgExternalDiffEngine == 'wikidiff' && !function_exists( 'wikidiff_do_diff' ) ) {
 746                         wfProfileIn( __METHOD__ . '-php_wikidiff.so' );
 747                         wfSuppressWarnings();
 748                         dl( 'php_wikidiff.so' );
 749                         wfRestoreWarnings();
 750                         wfProfileOut( __METHOD__ . '-php_wikidiff.so' );
 751                 }
 752                 else if ( $wgExternalDiffEngine == 'wikidiff2' && !function_exists( 'wikidiff2_do_diff' ) ) {
 753                         wfProfileIn( __METHOD__ . '-php_wikidiff2.so' );
 754                         wfSuppressWarnings();
 755                         dl( 'php_wikidiff2.so' );
 756                         wfRestoreWarnings();
 757                         wfProfileOut( __METHOD__ . '-php_wikidiff2.so' );
 758                 }
 759         }
 760
 761         /**
 762          * Generate a diff, no caching
 763          * $otext and $ntext must be already segmented
 764          */
 765         function generateDiffBody( $otext, $ntext ) {
 766                 global $wgExternalDiffEngine, $wgContLang;
 767
 768                 $otext = str_replace( "\r\n", "\n", $otext );
 769                 $ntext = str_replace( "\r\n", "\n", $ntext );
 770
 771                 $this->initDiffEngines();
 772
 773                 if ( $wgExternalDiffEngine == 'wikidiff' && function_exists( 'wikidiff_do_diff' ) ) {
 774                         # For historical reasons, external diff engine expects
 775                         # input text to be HTML-escaped already
 776                         $otext = htmlspecialchars ( $wgContLang->segmentForDiff( $otext ) );
 777                         $ntext = htmlspecialchars ( $wgContLang->segmentForDiff( $ntext ) );
 778                         return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) .
 779                         $this->debug( 'wikidiff1' );
 780                 }
 781
 782                 if ( $wgExternalDiffEngine == 'wikidiff2' && function_exists( 'wikidiff2_do_diff' ) ) {
 783                         # Better external diff engine, the 2 may some day be dropped
 784                         # This one does the escaping and segmenting itself
 785                         wfProfileIn( 'wikidiff2_do_diff' );
 786                         $text = wikidiff2_do_diff( $otext, $ntext, 2 );
 787                         $text .= $this->debug( 'wikidiff2' );
 788                         wfProfileOut( 'wikidiff2_do_diff' );
 789                         return $text;
 790                 }
 791                 if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) {
 792                         # Diff via the shell
 793                         global $wgTmpDirectory;
 794                         $tempName1 = tempnam( $wgTmpDirectory, 'diff_' );
 795                         $tempName2 = tempnam( $wgTmpDirectory, 'diff_' );
 796
 797                         $tempFile1 = fopen( $tempName1, "w" );
 798                         if ( !$tempFile1 ) {
 799                                 wfProfileOut( __METHOD__ );
 800                                 return false;
 801                         }
 802                         $tempFile2 = fopen( $tempName2, "w" );
 803                         if ( !$tempFile2 ) {
 804                                 wfProfileOut( __METHOD__ );
 805                                 return false;
 806                         }
 807                         fwrite( $tempFile1, $otext );
 808                         fwrite( $tempFile2, $ntext );
 809                         fclose( $tempFile1 );
 810                         fclose( $tempFile2 );
 811                         $cmd = wfEscapeShellArg( $wgExternalDiffEngine, $tempName1, $tempName2 );
 812                         wfProfileIn( __METHOD__ . "-shellexec" );
 813                         $difftext = wfShellExec( $cmd );
 814                         $difftext .= $this->debug( "external $wgExternalDiffEngine" );
 815                         wfProfileOut( __METHOD__ . "-shellexec" );
 816                         unlink( $tempName1 );
 817                         unlink( $tempName2 );
 818                         return $difftext;
 819                 }
 820
 821                 # Native PHP diff
 822                 $ota = explode( "\n", $wgContLang->segmentForDiff( $otext ) );
 823                 $nta = explode( "\n", $wgContLang->segmentForDiff( $ntext ) );
 824                 $diffs = new Diff( $ota, $nta );
 825                 $formatter = new TableDiffFormatter();
 826                 return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) .
 827                 $this->debug();
 828         }
 829
 830         /**
 831          * Generate a debug comment indicating diff generating time,
 832          * server node, and generator backend.
 833          */
 834         protected function debug( $generator="internal" ) {
 835                 global $wgShowHostnames;
 836                 $data = array( $generator );
 837                 if( $wgShowHostnames ) {
 838                         $data[] = wfHostname();
 839                 }
 840                 $data[] = wfTimestamp( TS_DB );
 841                 return "<!-- diff generator: " .
 842                 implode( " ",
 843                 array_map(
 844                                         "htmlspecialchars",
 845                 $data ) ) .
 846                         " -->\n";
 847         }
 848
 849         /**
 850          * Replace line numbers with the text in the user's language
 851          */
 852         function localiseLineNumbers( $text ) {
 853                 return preg_replace_callback( '/<!--LINE (\d+)-->/',
 854                 array( &$this, 'localiseLineNumbersCb' ), $text );
 855         }
 856
 857         function localiseLineNumbersCb( $matches ) {
 858                 global $wgLang;
 859                 if ( $matches[1] === '1' && $this->mReducedLineNumbers ) return '';
 860                 return wfMsgExt( 'lineno', 'escape', $wgLang->formatNum( $matches[1] ) );
 861         }
 862
 863
 864         /**
 865          * If there are revisions between the ones being compared, return a note saying so.
 866          */
 867         function getMultiNotice() {
 868                 if ( !is_object($this->mOldRev) || !is_object($this->mNewRev) )
 869                 return '';
 870
 871                 if( !$this->mOldPage->equals( $this->mNewPage ) ) {
 872                         // Comparing two different pages? Count would be meaningless.
 873                         return '';
 874                 }
 875
 876                 $oldid = $this->mOldRev->getId();
 877                 $newid = $this->mNewRev->getId();
 878                 if ( $oldid > $newid ) {
 879                         $tmp = $oldid; $oldid = $newid; $newid = $tmp;
 880                 }
 881
 882                 $n = $this->mTitle->countRevisionsBetween( $oldid, $newid );
 883                 if ( !$n )
 884                 return '';
 885
 886                 return wfMsgExt( 'diff-multi', array( 'parseinline' ), $n );
 887         }
 888
 889
 890         /**
 891          * Add the header to a diff body
 892          */
 893         static function addHeader( $diff, $otitle, $ntitle, $multi = '' ) {
 894                 $colspan = 1;
 895                 $header = "<table class='diff'>";
 896                 if( $diff ) { // Safari/Chrome show broken output if cols not used
 897                         $header .= "
 898                         <col class='diff-marker' />
 899                         <col class='diff-content' />
 900                         <col class='diff-marker' />
 901                         <col class='diff-content' />";
 902                         $colspan = 2;
 903                 }
 904                 $header .= "
 905                 <tr valign='top'>
 906                 <td colspan='$colspan' class='diff-otitle'>{$otitle}</td>
 907                 <td colspan='$colspan' class='diff-ntitle'>{$ntitle}</td>
 908                 </tr>";
 909
 910                 if ( $multi != '' )
 911                 $header .= "<tr><td colspan='4' align='center' class='diff-multi'>{$multi}</td></tr>";
 912
 913                 return $header . $diff . "</table>";
 914         }
 915
 916         /**
 917          * Use specified text instead of loading from the database
 918          */
 919         function setText( $oldText, $newText ) {
 920                 $this->mOldtext = $oldText;
 921                 $this->mNewtext = $newText;
 922                 $this->mTextLoaded = 2;
 923                 $this->mRevisionsLoaded = true;
 924         }
 925
 926         /**
 927          * Load revision metadata for the specified articles. If newid is 0, then compare
 928          * the old article in oldid to the current article; if oldid is 0, then
 929          * compare the current article to the immediately previous one (ignoring the
 930          * value of newid).
 931          *
 932          * If oldid is false, leave the corresponding revision object set
 933          * to false. This is impossible via ordinary user input, and is provided for
 934          * API convenience.
 935          */
 936         function loadRevisionData() {
 937                 global $wgLang, $wgUser;
 938                 if ( $this->mRevisionsLoaded ) {
 939                         return true;
 940                 } else {
 941                         // Whether it succeeds or fails, we don't want to try again
 942                         $this->mRevisionsLoaded = true;
 943                 }
 944
 945                 // Load the new revision object
 946                 $this->mNewRev = $this->mNewid
 947                         ? Revision::newFromId( $this->mNewid )
 948                         : Revision::newFromTitle( $this->mTitle );
 949                 if( !$this->mNewRev instanceof Revision )
 950                         return false;
 951
 952                 // Update the new revision ID in case it was 0 (makes life easier doing UI stuff)
 953                 $this->mNewid = $this->mNewRev->getId();
 954
 955                 // Check if page is editable
 956                 $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
 957
 958                 // Set assorted variables
 959                 $timestamp = $wgLang->timeanddate( $this->mNewRev->getTimestamp(), true );
 960                 $dateofrev = $wgLang->date( $this->mNewRev->getTimestamp(), true );
 961                 $timeofrev = $wgLang->time( $this->mNewRev->getTimestamp(), true );
 962                 $this->mNewPage = $this->mNewRev->getTitle();
 963                 if( $this->mNewRev->isCurrent() ) {
 964                         $newLink = $this->mNewPage->escapeLocalUrl( array(
 965                                 'oldid' => $this->mNewid
 966                         ) );
 967                         $this->mPagetitle = htmlspecialchars( wfMsg(
 968                                 'currentrev-asof',
 969                                 $timestamp,
 970                                 $dateofrev,
 971                                 $timeofrev
 972                         ) );
 973                         $newEdit = $this->mNewPage->escapeLocalUrl( array(
 974                                 'action' => 'edit'
 975                         ) );
 976
 977                         $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
 978                         $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
 979                 } else {
 980                         $newLink = $this->mNewPage->escapeLocalUrl( array(
 981                                 'oldid' => $this->mNewid
 982                         ) );
 983                         $newEdit = $this->mNewPage->escapeLocalUrl( array(
 984                                 'action' => 'edit',
 985                                 'oldid' => $this->mNewid
 986                         ) );
 987                         $this->mPagetitle = htmlspecialchars( wfMsg(
 988                                 'revisionasof',
 989                                 $timestamp,
 990                                 $dateofrev,
 991                                 $timeofrev
 992                         ) );
 993
 994                         $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
 995                         $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
 996                 }
 997                 if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 998                         $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";
 999                 } else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
1000                         $this->mNewtitle = "<span class='history-deleted'>{$this->mNewtitle}</span>";
1001                 }
1002
1003                 // Load the old revision object
1004                 $this->mOldRev = false;
1005                 if( $this->mOldid ) {
1006                         $this->mOldRev = Revision::newFromId( $this->mOldid );
1007                 } elseif ( $this->mOldid === 0 ) {
1008                         $rev = $this->mNewRev->getPrevious();
1009                         if( $rev ) {
1010                                 $this->mOldid = $rev->getId();
1011                                 $this->mOldRev = $rev;
1012                         } else {
1013                                 // No previous revision; mark to show as first-version only.
1014                                 $this->mOldid = false;
1015                                 $this->mOldRev = false;
1016                         }
1017                 }/* elseif ( $this->mOldid === false ) leave mOldRev false; */
1018
1019                 if( is_null( $this->mOldRev ) ) {
1020                         return false;
1021                 }
1022
1023                 if ( $this->mOldRev ) {
1024                         $this->mOldPage = $this->mOldRev->getTitle();
1025
1026                         $t = $wgLang->timeanddate( $this->mOldRev->getTimestamp(), true );
1027                         $dateofrev = $wgLang->date( $this->mOldRev->getTimestamp(), true );
1028                         $timeofrev = $wgLang->time( $this->mOldRev->getTimestamp(), true );
1029                         $oldLink = $this->mOldPage->escapeLocalUrl( array(
1030                                 'oldid' => $this->mOldid
1031                         ) );
1032                         $oldEdit = $this->mOldPage->escapeLocalUrl( array(
1033                                 'action' => 'edit',
1034                                 'oldid' => $this->mOldid
1035                         ) );
1036                         $this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t, $dateofrev, $timeofrev ) );
1037
1038                         $this->mOldtitle = "<a href='$oldLink'>{$this->mOldPagetitle}</a>"
1039                         . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
1040                         // Add an "undo" link
1041                         $newUndo = $this->mNewPage->escapeLocalUrl( array(
1042                                 'action' => 'edit',
1043                                 'undoafter' => $this->mOldid,
1044                                 'undo' => $this->mNewid
1045                         ) );
1046                         $htmlLink = htmlspecialchars( wfMsg( 'editundo' ) );
1047                         $htmlTitle = $wgUser->getSkin()->tooltip( 'undo' );
1048                         if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) {
1049                                 $this->mNewtitle .= " (<a href='$newUndo' $htmlTitle>" . $htmlLink . "</a>)";
1050                         }
1051
1052                         if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) {
1053                                 $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';
1054                         } else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) {
1055                                 $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';
1056                         }
1057                 }
1058
1059                 return true;
1060         }
1061
1062         /**
1063          * Load the text of the revisions, as well as revision data.
1064          */
1065         function loadText() {
1066                 if ( $this->mTextLoaded == 2 ) {
1067                         return true;
1068                 } else {
1069                         // Whether it succeeds or fails, we don't want to try again
1070                         $this->mTextLoaded = 2;
1071                 }
1072
1073                 if ( !$this->loadRevisionData() ) {
1074                         return false;
1075                 }
1076                 if ( $this->mOldRev ) {
1077                         $this->mOldtext = $this->mOldRev->getText( Revision::FOR_THIS_USER );
1078                         if ( $this->mOldtext === false ) {
1079                                 return false;
1080                         }
1081                 }
1082                 if ( $this->mNewRev ) {
1083                         $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
1084                         if ( $this->mNewtext === false ) {
1085                                 return false;
1086                         }
1087                 }
1088                 return true;
1089         }
1090
1091         /**
1092          * Load the text of the new revision, not the old one
1093          */
1094         function loadNewText() {
1095                 if ( $this->mTextLoaded >= 1 ) {
1096                         return true;
1097                 } else {
1098                         $this->mTextLoaded = 1;
1099                 }
1100                 if ( !$this->loadRevisionData() ) {
1101                         return false;
1102                 }
1103                 $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
1104                 return true;
1105         }
1106 }
1107
1108 // A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
1109 //
1110 // Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
1111 // You may copy this code freely under the conditions of the GPL.
1112 //
1113
1114 define('USE_ASSERTS', function_exists('assert'));
1115
1116 /**
1117  * @todo document
1118  * @private
1119  * @ingroup DifferenceEngine
1120  */
1121 class _DiffOp {
1122         var $type;
1123         var $orig;
1124         var $closing;
1125
1126         function reverse() {
1127                 trigger_error('pure virtual', E_USER_ERROR);
1128         }
1129
1130         function norig() {
1131                 return $this->orig ? sizeof($this->orig) : 0;
1132         }
1133
1134         function nclosing() {
1135                 return $this->closing ? sizeof($this->closing) : 0;
1136         }
1137 }
1138
1139 /**
1140  * @todo document
1141  * @private
1142  * @ingroup DifferenceEngine
1143  */
1144 class _DiffOp_Copy extends _DiffOp {
1145         var $type = 'copy';
1146
1147         function _DiffOp_Copy ($orig, $closing = false) {
1148                 if (!is_array($closing))
1149                 $closing = $orig;
1150                 $this->orig = $orig;
1151                 $this->closing = $closing;
1152         }
1153
1154         function reverse() {
1155                 return new _DiffOp_Copy($this->closing, $this->orig);
1156         }
1157 }
1158
1159 /**
1160  * @todo document
1161  * @private
1162  * @ingroup DifferenceEngine
1163  */
1164 class _DiffOp_Delete extends _DiffOp {
1165         var $type = 'delete';
1166
1167         function _DiffOp_Delete ($lines) {
1168                 $this->orig = $lines;
1169                 $this->closing = false;
1170         }
1171
1172         function reverse() {
1173                 return new _DiffOp_Add($this->orig);
1174         }
1175 }
1176
1177 /**
1178  * @todo document
1179  * @private
1180  * @ingroup DifferenceEngine
1181  */
1182 class _DiffOp_Add extends _DiffOp {
1183         var $type = 'add';
1184
1185         function _DiffOp_Add ($lines) {
1186                 $this->closing = $lines;
1187                 $this->orig = false;
1188         }
1189
1190         function reverse() {
1191                 return new _DiffOp_Delete($this->closing);
1192         }
1193 }
1194
1195 /**
1196  * @todo document
1197  * @private
1198  * @ingroup DifferenceEngine
1199  */
1200 class _DiffOp_Change extends _DiffOp {
1201         var $type = 'change';
1202
1203         function _DiffOp_Change ($orig, $closing) {
1204                 $this->orig = $orig;
1205                 $this->closing = $closing;
1206         }
1207
1208         function reverse() {
1209                 return new _DiffOp_Change($this->closing, $this->orig);
1210         }
1211 }
1212
1213 /**
1214  * Class used internally by Diff to actually compute the diffs.
1215  *
1216  * The algorithm used here is mostly lifted from the perl module
1217  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
1218  *       http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
1219  *
1220  * More ideas are taken from:
1221  *       http://www.ics.uci.edu/~eppstein/161/960229.html
1222  *
1223  * Some ideas are (and a bit of code) are from from analyze.c, from GNU
1224  * diffutils-2.7, which can be found at:
1225  *       ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
1226  *
1227  * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
1228  * are my own.
1229  *
1230  * Line length limits for robustness added by Tim Starling, 2005-08-31
1231  * Alternative implementation added by Guy Van den Broeck, 2008-07-30
1232  *
1233  * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
1234  * @private
1235  * @ingroup DifferenceEngine
1236  */
1237 class _DiffEngine {
1238
1239         const MAX_XREF_LENGTH =  10000;
1240
1241         function diff ($from_lines, $to_lines){
1242                 wfProfileIn( __METHOD__ );
1243
1244                 // Diff and store locally
1245                 $this->diff_local($from_lines, $to_lines);
1246
1247                 // Merge edits when possible
1248                 $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
1249                 $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
1250
1251                 // Compute the edit operations.
1252                 $n_from = sizeof($from_lines);
1253                 $n_to = sizeof($to_lines);
1254
1255                 $edits = array();
1256                 $xi = $yi = 0;
1257                 while ($xi < $n_from || $yi < $n_to) {
1258                         USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
1259                         USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
1260
1261                         // Skip matching "snake".
1262                         $copy = array();
1263                         while ( $xi < $n_from && $yi < $n_to
1264                         && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
1265                                 $copy[] = $from_lines[$xi++];
1266                                 ++$yi;
1267                         }
1268                         if ($copy)
1269                         $edits[] = new _DiffOp_Copy($copy);
1270
1271                         // Find deletes & adds.
1272                         $delete = array();
1273                         while ($xi < $n_from && $this->xchanged[$xi])
1274                         $delete[] = $from_lines[$xi++];
1275
1276                         $add = array();
1277                         while ($yi < $n_to && $this->ychanged[$yi])
1278                         $add[] = $to_lines[$yi++];
1279
1280                         if ($delete && $add)
1281                         $edits[] = new _DiffOp_Change($delete, $add);
1282                         elseif ($delete)
1283                         $edits[] = new _DiffOp_Delete($delete);
1284                         elseif ($add)
1285                         $edits[] = new _DiffOp_Add($add);
1286                 }
1287                 wfProfileOut( __METHOD__ );
1288                 return $edits;
1289         }
1290
1291         function diff_local ($from_lines, $to_lines) {
1292                 global $wgExternalDiffEngine;
1293                 wfProfileIn( __METHOD__);
1294
1295                 if($wgExternalDiffEngine == 'wikidiff3'){
1296                         // wikidiff3
1297                         $wikidiff3 = new WikiDiff3();
1298                         $wikidiff3->diff($from_lines, $to_lines);
1299                         $this->xchanged = $wikidiff3->removed;
1300                         $this->ychanged = $wikidiff3->added;
1301                         unset($wikidiff3);
1302                 }else{
1303                         // old diff
1304                         $n_from = sizeof($from_lines);
1305                         $n_to = sizeof($to_lines);
1306                         $this->xchanged = $this->ychanged = array();
1307                         $this->xv = $this->yv = array();
1308                         $this->xind = $this->yind = array();
1309                         unset($this->seq);
1310                         unset($this->in_seq);
1311                         unset($this->lcs);
1312
1313                         // Skip leading common lines.
1314                         for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
1315                                 if ($from_lines[$skip] !== $to_lines[$skip])
1316                                 break;
1317                                 $this->xchanged[$skip] = $this->ychanged[$skip] = false;
1318                         }
1319                         // Skip trailing common lines.
1320                         $xi = $n_from; $yi = $n_to;
1321                         for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
1322                                 if ($from_lines[$xi] !== $to_lines[$yi])
1323                                 break;
1324                                 $this->xchanged[$xi] = $this->ychanged[$yi] = false;
1325                         }
1326
1327                         // Ignore lines which do not exist in both files.
1328                         for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
1329                                 $xhash[$this->_line_hash($from_lines[$xi])] = 1;
1330                         }
1331
1332                         for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
1333                                 $line = $to_lines[$yi];
1334                                 if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )
1335                                 continue;
1336                                 $yhash[$this->_line_hash($line)] = 1;
1337                                 $this->yv[] = $line;
1338                                 $this->yind[] = $yi;
1339                         }
1340                         for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
1341                                 $line = $from_lines[$xi];
1342                                 if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )
1343                                 continue;
1344                                 $this->xv[] = $line;
1345                                 $this->xind[] = $xi;
1346                         }
1347
1348                         // Find the LCS.
1349                         $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
1350                 }
1351                 wfProfileOut( __METHOD__ );
1352         }
1353
1354         /**
1355          * Returns the whole line if it's small enough, or the MD5 hash otherwise
1356          */
1357         function _line_hash( $line ) {
1358                 if ( strlen( $line ) > self::MAX_XREF_LENGTH ) {
1359                         return md5( $line );
1360                 } else {
1361                         return $line;
1362                 }
1363         }
1364
1365         /* Divide the Largest Common Subsequence (LCS) of the sequences
1366          * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
1367          * sized segments.
1368          *
1369          * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
1370          * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
1371          * sub sequences.  The first sub-sequence is contained in [X0, X1),
1372          * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
1373          * that (X0, Y0) == (XOFF, YOFF) and
1374          * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
1375          *
1376          * This function assumes that the first lines of the specified portions
1377          * of the two files do not match, and likewise that the last lines do not
1378          * match.  The caller must trim matching lines from the beginning and end
1379          * of the portions it is going to specify.
1380          */
1381         function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
1382                 $flip = false;
1383
1384                 if ($xlim - $xoff > $ylim - $yoff) {
1385                         // Things seems faster (I'm not sure I understand why)
1386                         // when the shortest sequence in X.
1387                         $flip = true;
1388                         list ($xoff, $xlim, $yoff, $ylim)
1389                         = array( $yoff, $ylim, $xoff, $xlim);
1390                 }
1391
1392                 if ($flip)
1393                 for ($i = $ylim - 1; $i >= $yoff; $i--)
1394                 $ymatches[$this->xv[$i]][] = $i;
1395                 else
1396                 for ($i = $ylim - 1; $i >= $yoff; $i--)
1397                 $ymatches[$this->yv[$i]][] = $i;
1398
1399                 $this->lcs = 0;
1400                 $this->seq[0]= $yoff - 1;
1401                 $this->in_seq = array();
1402                 $ymids[0] = array();
1403
1404                 $numer = $xlim - $xoff + $nchunks - 1;
1405                 $x = $xoff;
1406                 for ($chunk = 0; $chunk < $nchunks; $chunk++) {
1407                         if ($chunk > 0)
1408                         for ($i = 0; $i <= $this->lcs; $i++)
1409                         $ymids[$i][$chunk-1] = $this->seq[$i];
1410
1411                         $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
1412                         for ( ; $x < $x1; $x++) {
1413                                 $line = $flip ? $this->yv[$x] : $this->xv[$x];
1414                                 if (empty($ymatches[$line]))
1415                                 continue;
1416                                 $matches = $ymatches[$line];
1417                                 reset($matches);
1418                                 while (list ($junk, $y) = each($matches))
1419                                 if (empty($this->in_seq[$y])) {
1420                                         $k = $this->_lcs_pos($y);
1421                                         USE_ASSERTS && assert($k > 0);
1422                                         $ymids[$k] = $ymids[$k-1];
1423                                         break;
1424                                 }
1425                                 while (list ( /* $junk */, $y) = each($matches)) {
1426                                         if ($y > $this->seq[$k-1]) {
1427                                                 USE_ASSERTS && assert($y < $this->seq[$k]);
1428                                                 // Optimization: this is a common case:
1429                                                 //      next match is just replacing previous match.
1430                                                 $this->in_seq[$this->seq[$k]] = false;
1431                                                 $this->seq[$k] = $y;
1432                                                 $this->in_seq[$y] = 1;
1433                                         } else if (empty($this->in_seq[$y])) {
1434                                                 $k = $this->_lcs_pos($y);
1435                                                 USE_ASSERTS && assert($k > 0);
1436                                                 $ymids[$k] = $ymids[$k-1];
1437                                         }
1438                                 }
1439                         }
1440                 }
1441
1442                 $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
1443                 $ymid = $ymids[$this->lcs];
1444                 for ($n = 0; $n < $nchunks - 1; $n++) {
1445                         $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
1446                         $y1 = $ymid[$n] + 1;
1447                         $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
1448                 }
1449                 $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
1450
1451                 return array($this->lcs, $seps);
1452         }
1453
1454         function _lcs_pos ($ypos) {
1455                 $end = $this->lcs;
1456                 if ($end == 0 || $ypos > $this->seq[$end]) {
1457                         $this->seq[++$this->lcs] = $ypos;
1458                         $this->in_seq[$ypos] = 1;
1459                         return $this->lcs;
1460                 }
1461
1462                 $beg = 1;
1463                 while ($beg < $end) {
1464                         $mid = (int)(($beg + $end) / 2);
1465                         if ( $ypos > $this->seq[$mid] )
1466                         $beg = $mid + 1;
1467                         else
1468                         $end = $mid;
1469                 }
1470
1471                 USE_ASSERTS && assert($ypos != $this->seq[$end]);
1472
1473                 $this->in_seq[$this->seq[$end]] = false;
1474                 $this->seq[$end] = $ypos;
1475                 $this->in_seq[$ypos] = 1;
1476                 return $end;
1477         }
1478
1479         /* Find LCS of two sequences.
1480          *
1481          * The results are recorded in the vectors $this->{x,y}changed[], by
1482          * storing a 1 in the element for each line that is an insertion
1483          * or deletion (ie. is not in the LCS).
1484          *
1485          * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
1486          *
1487          * Note that XLIM, YLIM are exclusive bounds.
1488          * All line numbers are origin-0 and discarded lines are not counted.
1489          */
1490         function _compareseq ($xoff, $xlim, $yoff, $ylim) {
1491                 // Slide down the bottom initial diagonal.
1492                 while ($xoff < $xlim && $yoff < $ylim
1493                 && $this->xv[$xoff] == $this->yv[$yoff]) {
1494                         ++$xoff;
1495                         ++$yoff;
1496                 }
1497
1498                 // Slide up the top initial diagonal.
1499                 while ($xlim > $xoff && $ylim > $yoff
1500                 && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
1501                         --$xlim;
1502                         --$ylim;
1503                 }
1504
1505                 if ($xoff == $xlim || $yoff == $ylim)
1506                 $lcs = 0;
1507                 else {
1508                         // This is ad hoc but seems to work well.
1509                         //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
1510                         //$nchunks = max(2,min(8,(int)$nchunks));
1511                         $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
1512                         list ($lcs, $seps)
1513                         = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
1514                 }
1515
1516                 if ($lcs == 0) {
1517                         // X and Y sequences have no common subsequence:
1518                         // mark all changed.
1519                         while ($yoff < $ylim)
1520                         $this->ychanged[$this->yind[$yoff++]] = 1;
1521                         while ($xoff < $xlim)
1522                         $this->xchanged[$this->xind[$xoff++]] = 1;
1523                 } else {
1524                         // Use the partitions to split this problem into subproblems.
1525                         reset($seps);
1526                         $pt1 = $seps[0];
1527                         while ($pt2 = next($seps)) {
1528                                 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
1529                                 $pt1 = $pt2;
1530                         }
1531                 }
1532         }
1533
1534         /* Adjust inserts/deletes of identical lines to join changes
1535          * as much as possible.
1536          *
1537          * We do something when a run of changed lines include a
1538          * line at one end and has an excluded, identical line at the other.
1539          * We are free to choose which identical line is included.
1540          * `compareseq' usually chooses the one at the beginning,
1541          * but usually it is cleaner to consider the following identical line
1542          * to be the "change".
1543          *
1544          * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
1545          */
1546         function _shift_boundaries ($lines, &$changed, $other_changed) {
1547                 wfProfileIn( __METHOD__ );
1548                 $i = 0;
1549                 $j = 0;
1550
1551                 USE_ASSERTS && assert('sizeof($lines) == sizeof($changed)');
1552                 $len = sizeof($lines);
1553                 $other_len = sizeof($other_changed);
1554
1555                 while (1) {
1556                         /*
1557                          * Scan forwards to find beginning of another run of changes.
1558                          * Also keep track of the corresponding point in the other file.
1559                          *
1560                          * Throughout this code, $i and $j are adjusted together so that
1561                          * the first $i elements of $changed and the first $j elements
1562                          * of $other_changed both contain the same number of zeros
1563                          * (unchanged lines).
1564                          * Furthermore, $j is always kept so that $j == $other_len or
1565                          * $other_changed[$j] == false.
1566                          */
1567                         while ($j < $other_len && $other_changed[$j])
1568                         $j++;
1569
1570                         while ($i < $len && ! $changed[$i]) {
1571                                 USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1572                                 $i++; $j++;
1573                                 while ($j < $other_len && $other_changed[$j])
1574                                 $j++;
1575                         }
1576
1577                         if ($i == $len)
1578                         break;
1579
1580                         $start = $i;
1581
1582                         // Find the end of this run of changes.
1583                         while (++$i < $len && $changed[$i])
1584                         continue;
1585
1586                         do {
1587                                 /*
1588                                  * Record the length of this run of changes, so that
1589                                  * we can later determine whether the run has grown.
1590                                  */
1591                                 $runlength = $i - $start;
1592
1593                                 /*
1594                                  * Move the changed region back, so long as the
1595                                  * previous unchanged line matches the last changed one.
1596                                  * This merges with previous changed regions.
1597                                  */
1598                                 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
1599                                         $changed[--$start] = 1;
1600                                         $changed[--$i] = false;
1601                                         while ($start > 0 && $changed[$start - 1])
1602                                         $start--;
1603                                         USE_ASSERTS && assert('$j > 0');
1604                                         while ($other_changed[--$j])
1605                                         continue;
1606                                         USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1607                                 }
1608
1609                                 /*
1610                                  * Set CORRESPONDING to the end of the changed run, at the last
1611                                  * point where it corresponds to a changed run in the other file.
1612                                  * CORRESPONDING == LEN means no such point has been found.
1613                                  */
1614                                 $corresponding = $j < $other_len ? $i : $len;
1615
1616                                 /*
1617                                  * Move the changed region forward, so long as the
1618                                  * first changed line matches the following unchanged one.
1619                                  * This merges with following changed regions.
1620                                  * Do this second, so that if there are no merges,
1621                                  * the changed region is moved forward as far as possible.
1622                                  */
1623                                 while ($i < $len && $lines[$start] == $lines[$i]) {
1624                                         $changed[$start++] = false;
1625                                         $changed[$i++] = 1;
1626                                         while ($i < $len && $changed[$i])
1627                                         $i++;
1628
1629                                         USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1630                                         $j++;
1631                                         if ($j < $other_len && $other_changed[$j]) {
1632                                                 $corresponding = $i;
1633                                                 while ($j < $other_len && $other_changed[$j])
1634                                                 $j++;
1635                                         }
1636                                 }
1637                         } while ($runlength != $i - $start);
1638
1639                         /*
1640                          * If possible, move the fully-merged run of changes
1641                          * back to a corresponding run in the other file.
1642                          */
1643                         while ($corresponding < $i) {
1644                                 $changed[--$start] = 1;
1645                                 $changed[--$i] = 0;
1646                                 USE_ASSERTS && assert('$j > 0');
1647                                 while ($other_changed[--$j])
1648                                 continue;
1649                                 USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1650                         }
1651                 }
1652                 wfProfileOut( __METHOD__ );
1653         }
1654 }
1655
1656 /**
1657  * Class representing a 'diff' between two sequences of strings.
1658  * @todo document
1659  * @private
1660  * @ingroup DifferenceEngine
1661  */
1662 class Diff
1663 {
1664         var $edits;
1665
1666         /**
1667          * Constructor.
1668          * Computes diff between sequences of strings.
1669          *
1670          * @param $from_lines array An array of strings.
1671          *                (Typically these are lines from a file.)
1672          * @param $to_lines array An array of strings.
1673          */
1674         function Diff($from_lines, $to_lines) {
1675                 $eng = new _DiffEngine;
1676                 $this->edits = $eng->diff($from_lines, $to_lines);
1677                 //$this->_check($from_lines, $to_lines);
1678         }
1679
1680         /**
1681          * Compute reversed Diff.
1682          *
1683          * SYNOPSIS:
1684          *
1685          *      $diff = new Diff($lines1, $lines2);
1686          *      $rev = $diff->reverse();
1687          * @return object A Diff object representing the inverse of the
1688          *                                original diff.
1689          */
1690         function reverse () {
1691                 $rev = $this;
1692                 $rev->edits = array();
1693                 foreach ($this->edits as $edit) {
1694                         $rev->edits[] = $edit->reverse();
1695                 }
1696                 return $rev;
1697         }
1698
1699         /**
1700          * Check for empty diff.
1701          *
1702          * @return bool True iff two sequences were identical.
1703          */
1704         function isEmpty () {
1705                 foreach ($this->edits as $edit) {
1706                         if ($edit->type != 'copy')
1707                         return false;
1708                 }
1709                 return true;
1710         }
1711
1712         /**
1713          * Compute the length of the Longest Common Subsequence (LCS).
1714          *
1715          * This is mostly for diagnostic purposed.
1716          *
1717          * @return int The length of the LCS.
1718          */
1719         function lcs () {
1720                 $lcs = 0;
1721                 foreach ($this->edits as $edit) {
1722                         if ($edit->type == 'copy')
1723                         $lcs += sizeof($edit->orig);
1724                 }
1725                 return $lcs;
1726         }
1727
1728         /**
1729          * Get the original set of lines.
1730          *
1731          * This reconstructs the $from_lines parameter passed to the
1732          * constructor.
1733          *
1734          * @return array The original sequence of strings.
1735          */
1736         function orig() {
1737                 $lines = array();
1738
1739                 foreach ($this->edits as $edit) {
1740                         if ($edit->orig)
1741                         array_splice($lines, sizeof($lines), 0, $edit->orig);
1742                 }
1743                 return $lines;
1744         }
1745
1746         /**
1747          * Get the closing set of lines.
1748          *
1749          * This reconstructs the $to_lines parameter passed to the
1750          * constructor.
1751          *
1752          * @return array The sequence of strings.
1753          */
1754         function closing() {
1755                 $lines = array();
1756
1757                 foreach ($this->edits as $edit) {
1758                         if ($edit->closing)
1759                         array_splice($lines, sizeof($lines), 0, $edit->closing);
1760                 }
1761                 return $lines;
1762         }
1763
1764         /**
1765          * Check a Diff for validity.
1766          *
1767          * This is here only for debugging purposes.
1768          */
1769         function _check ($from_lines, $to_lines) {
1770                 wfProfileIn( __METHOD__ );
1771                 if (serialize($from_lines) != serialize($this->orig()))
1772                 trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
1773                 if (serialize($to_lines) != serialize($this->closing()))
1774                 trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
1775
1776                 $rev = $this->reverse();
1777                 if (serialize($to_lines) != serialize($rev->orig()))
1778                 trigger_error("Reversed original doesn't match", E_USER_ERROR);
1779                 if (serialize($from_lines) != serialize($rev->closing()))
1780                 trigger_error("Reversed closing doesn't match", E_USER_ERROR);
1781
1782
1783                 $prevtype = 'none';
1784                 foreach ($this->edits as $edit) {
1785                         if ( $prevtype == $edit->type )
1786                         trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
1787                         $prevtype = $edit->type;
1788                 }
1789
1790                 $lcs = $this->lcs();
1791                 trigger_error('Diff okay: LCS = '.$lcs, E_USER_NOTICE);
1792                 wfProfileOut( __METHOD__ );
1793         }
1794 }
1795
1796 /**
1797  * @todo document, bad name.
1798  * @private
1799  * @ingroup DifferenceEngine
1800  */
1801 class MappedDiff extends Diff
1802 {
1803         /**
1804          * Constructor.
1805          *
1806          * Computes diff between sequences of strings.
1807          *
1808          * This can be used to compute things like
1809          * case-insensitve diffs, or diffs which ignore
1810          * changes in white-space.
1811          *
1812          * @param $from_lines array An array of strings.
1813          *      (Typically these are lines from a file.)
1814          *
1815          * @param $to_lines array An array of strings.
1816          *
1817          * @param $mapped_from_lines array This array should
1818          *      have the same size number of elements as $from_lines.
1819          *      The elements in $mapped_from_lines and
1820          *      $mapped_to_lines are what is actually compared
1821          *      when computing the diff.
1822          *
1823          * @param $mapped_to_lines array This array should
1824          *      have the same number of elements as $to_lines.
1825          */
1826         function MappedDiff($from_lines, $to_lines,
1827         $mapped_from_lines, $mapped_to_lines) {
1828                 wfProfileIn( __METHOD__ );
1829
1830                 assert(sizeof($from_lines) == sizeof($mapped_from_lines));
1831                 assert(sizeof($to_lines) == sizeof($mapped_to_lines));
1832
1833                 $this->Diff($mapped_from_lines, $mapped_to_lines);
1834
1835                 $xi = $yi = 0;
1836                 for ($i = 0; $i < sizeof($this->edits); $i++) {
1837                         $orig = &$this->edits[$i]->orig;
1838                         if (is_array($orig)) {
1839                                 $orig = array_slice($from_lines, $xi, sizeof($orig));
1840                                 $xi += sizeof($orig);
1841                         }
1842
1843                         $closing = &$this->edits[$i]->closing;
1844                         if (is_array($closing)) {
1845                                 $closing = array_slice($to_lines, $yi, sizeof($closing));
1846                                 $yi += sizeof($closing);
1847                         }
1848                 }
1849                 wfProfileOut( __METHOD__ );
1850         }
1851 }
1852
1853 /**
1854  * A class to format Diffs
1855  *
1856  * This class formats the diff in classic diff format.
1857  * It is intended that this class be customized via inheritance,
1858  * to obtain fancier outputs.
1859  * @todo document
1860  * @private
1861  * @ingroup DifferenceEngine
1862  */
1863 class DiffFormatter {
1864         /**
1865          * Number of leading context "lines" to preserve.
1866          *
1867          * This should be left at zero for this class, but subclasses
1868          * may want to set this to other values.
1869          */
1870         var $leading_context_lines = 0;
1871
1872         /**
1873          * Number of trailing context "lines" to preserve.
1874          *
1875          * This should be left at zero for this class, but subclasses
1876          * may want to set this to other values.
1877          */
1878         var $trailing_context_lines = 0;
1879
1880         /**
1881          * Format a diff.
1882          *
1883          * @param $diff object A Diff object.
1884          * @return string The formatted output.
1885          */
1886         function format($diff) {
1887                 wfProfileIn( __METHOD__ );
1888
1889                 $xi = $yi = 1;
1890                 $block = false;
1891                 $context = array();
1892
1893                 $nlead = $this->leading_context_lines;
1894                 $ntrail = $this->trailing_context_lines;
1895
1896                 $this->_start_diff();
1897
1898                 foreach ($diff->edits as $edit) {
1899                         if ($edit->type == 'copy') {
1900                                 if (is_array($block)) {
1901                                         if (sizeof($edit->orig) <= $nlead + $ntrail) {
1902                                                 $block[] = $edit;
1903                                         }
1904                                         else{
1905                                                 if ($ntrail) {
1906                                                         $context = array_slice($edit->orig, 0, $ntrail);
1907                                                         $block[] = new _DiffOp_Copy($context);
1908                                                 }
1909                                                 $this->_block($x0, $ntrail + $xi - $x0,
1910                                                 $y0, $ntrail + $yi - $y0,
1911                                                 $block);
1912                                                 $block = false;
1913                                         }
1914                                 }
1915                                 $context = $edit->orig;
1916                         }
1917                         else {
1918                                 if (! is_array($block)) {
1919                                         $context = array_slice($context, sizeof($context) - $nlead);
1920                                         $x0 = $xi - sizeof($context);
1921                                         $y0 = $yi - sizeof($context);
1922                                         $block = array();
1923                                         if ($context)
1924                                         $block[] = new _DiffOp_Copy($context);
1925                                 }
1926                                 $block[] = $edit;
1927                         }
1928
1929                         if ($edit->orig)
1930                         $xi += sizeof($edit->orig);
1931                         if ($edit->closing)
1932                         $yi += sizeof($edit->closing);
1933                 }
1934
1935                 if (is_array($block))
1936                 $this->_block($x0, $xi - $x0,
1937                 $y0, $yi - $y0,
1938                 $block);
1939
1940                 $end = $this->_end_diff();
1941                 wfProfileOut( __METHOD__ );
1942                 return $end;
1943         }
1944
1945         function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
1946                 wfProfileIn( __METHOD__ );
1947                 $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
1948                 foreach ($edits as $edit) {
1949                         if ($edit->type == 'copy')
1950                         $this->_context($edit->orig);
1951                         elseif ($edit->type == 'add')
1952                         $this->_added($edit->closing);
1953                         elseif ($edit->type == 'delete')
1954                         $this->_deleted($edit->orig);
1955                         elseif ($edit->type == 'change')
1956                         $this->_changed($edit->orig, $edit->closing);
1957                         else
1958                         trigger_error('Unknown edit type', E_USER_ERROR);
1959                 }
1960                 $this->_end_block();
1961                 wfProfileOut( __METHOD__ );
1962         }
1963
1964         function _start_diff() {
1965                 ob_start();
1966         }
1967
1968         function _end_diff() {
1969                 $val = ob_get_contents();
1970                 ob_end_clean();
1971                 return $val;
1972         }
1973
1974         function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1975                 if ($xlen > 1)
1976                 $xbeg .= "," . ($xbeg + $xlen - 1);
1977                 if ($ylen > 1)
1978                 $ybeg .= "," . ($ybeg + $ylen - 1);
1979
1980                 return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
1981         }
1982
1983         function _start_block($header) {
1984                 echo $header . "\n";
1985         }
1986
1987         function _end_block() {
1988         }
1989
1990         function _lines($lines, $prefix = ' ') {
1991                 foreach ($lines as $line)
1992                 echo "$prefix $line\n";
1993         }
1994
1995         function _context($lines) {
1996                 $this->_lines($lines);
1997         }
1998
1999         function _added($lines) {
2000                 $this->_lines($lines, '>');
2001         }
2002         function _deleted($lines) {
2003                 $this->_lines($lines, '<');
2004         }
2005
2006         function _changed($orig, $closing) {
2007                 $this->_deleted($orig);
2008                 echo "---\n";
2009                 $this->_added($closing);
2010         }
2011 }
2012
2013 /**
2014  * A formatter that outputs unified diffs
2015  * @ingroup DifferenceEngine
2016  */
2017
2018 class UnifiedDiffFormatter extends DiffFormatter {
2019         var $leading_context_lines = 2;
2020         var $trailing_context_lines = 2;
2021
2022         function _added($lines) {
2023                 $this->_lines($lines, '+');
2024         }
2025         function _deleted($lines) {
2026                 $this->_lines($lines, '-');
2027         }
2028         function _changed($orig, $closing) {
2029                 $this->_deleted($orig);
2030                 $this->_added($closing);
2031         }
2032         function _block_header($xbeg, $xlen, $ybeg, $ylen) {
2033                 return "@@ -$xbeg,$xlen +$ybeg,$ylen @@";
2034         }
2035 }
2036
2037 /**
2038  * A pseudo-formatter that just passes along the Diff::$edits array
2039  * @ingroup DifferenceEngine
2040  */
2041 class ArrayDiffFormatter extends DiffFormatter {
2042         function format($diff) {
2043                 $oldline = 1;
2044                 $newline = 1;
2045                 $retval = array();
2046                 foreach($diff->edits as $edit)
2047                 switch($edit->type) {
2048                         case 'add':
2049                                 foreach($edit->closing as $l) {
2050                                         $retval[] = array(
2051                                                         'action' => 'add',
2052                                                         'new'=> $l,
2053                                                         'newline' => $newline++
2054                                         );
2055                                 }
2056                                 break;
2057                         case 'delete':
2058                                 foreach($edit->orig as $l) {
2059                                         $retval[] = array(
2060                                                         'action' => 'delete',
2061                                                         'old' => $l,
2062                                                         'oldline' => $oldline++,
2063                                         );
2064                                 }
2065                                 break;
2066                         case 'change':
2067                                 foreach($edit->orig as $i => $l) {
2068                                         $retval[] = array(
2069                                                         'action' => 'change',
2070                                                         'old' => $l,
2071                                                         'new' => @$edit->closing[$i],
2072                                                         'oldline' => $oldline++,
2073                                                         'newline' => $newline++,
2074                                         );
2075                                 }
2076                                 break;
2077                         case 'copy':
2078                                 $oldline += count($edit->orig);
2079                                 $newline += count($edit->orig);
2080                 }
2081                 return $retval;
2082         }
2083 }
2084
2085 /**
2086  *      Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
2087  *
2088  */
2089
2090 define('NBSP', '&#160;'); // iso-8859-x non-breaking space.
2091
2092 /**
2093  * @todo document
2094  * @private
2095  * @ingroup DifferenceEngine
2096  */
2097 class _HWLDF_WordAccumulator {
2098         function _HWLDF_WordAccumulator () {
2099                 $this->_lines = array();
2100                 $this->_line = '';
2101                 $this->_group = '';
2102                 $this->_tag = '';
2103         }
2104
2105         function _flushGroup ($new_tag) {
2106                 if ($this->_group !== '') {
2107                         if ($this->_tag == 'ins')
2108                         $this->_line .= '<ins class="diffchange diffchange-inline">' .
2109                         htmlspecialchars ( $this->_group ) . '</ins>';
2110                         elseif ($this->_tag == 'del')
2111                         $this->_line .= '<del class="diffchange diffchange-inline">' .
2112                         htmlspecialchars ( $this->_group ) . '</del>';
2113                         else
2114                         $this->_line .= htmlspecialchars ( $this->_group );
2115                 }
2116                 $this->_group = '';
2117                 $this->_tag = $new_tag;
2118         }
2119
2120         function _flushLine ($new_tag) {
2121                 $this->_flushGroup($new_tag);
2122                 if ($this->_line != '')
2123                 array_push ( $this->_lines, $this->_line );
2124                 else
2125                 # make empty lines visible by inserting an NBSP
2126                 array_push ( $this->_lines, NBSP );
2127                 $this->_line = '';
2128         }
2129
2130         function addWords ($words, $tag = '') {
2131                 if ($tag != $this->_tag)
2132                 $this->_flushGroup($tag);
2133
2134                 foreach ($words as $word) {
2135                         // new-line should only come as first char of word.
2136                         if ($word == '')
2137                         continue;
2138                         if ($word[0] == "\n") {
2139                                 $this->_flushLine($tag);
2140                                 $word = substr($word, 1);
2141                         }
2142                         assert(!strstr($word, "\n"));
2143                         $this->_group .= $word;
2144                 }
2145         }
2146
2147         function getLines() {
2148                 $this->_flushLine('~done');
2149                 return $this->_lines;
2150         }
2151 }
2152
2153 /**
2154  * @todo document
2155  * @private
2156  * @ingroup DifferenceEngine
2157  */
2158 class WordLevelDiff extends MappedDiff {
2159         const MAX_LINE_LENGTH = 10000;
2160
2161         function WordLevelDiff ($orig_lines, $closing_lines) {
2162                 wfProfileIn( __METHOD__ );
2163
2164                 list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
2165                 list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
2166
2167                 $this->MappedDiff($orig_words, $closing_words,
2168                 $orig_stripped, $closing_stripped);
2169                 wfProfileOut( __METHOD__ );
2170         }
2171
2172         function _split($lines) {
2173                 wfProfileIn( __METHOD__ );
2174
2175                 $words = array();
2176                 $stripped = array();
2177                 $first = true;
2178                 foreach ( $lines as $line ) {
2179                         # If the line is too long, just pretend the entire line is one big word
2180                         # This prevents resource exhaustion problems
2181                         if ( $first ) {
2182                                 $first = false;
2183                         } else {
2184                                 $words[] = "\n";
2185                                 $stripped[] = "\n";
2186                         }
2187                         if ( strlen( $line ) > self::MAX_LINE_LENGTH ) {
2188                                 $words[] = $line;
2189                                 $stripped[] = $line;
2190                         } else {
2191                                 $m = array();
2192                                 if (preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
2193                                 $line, $m))
2194                                 {
2195                                         $words = array_merge( $words, $m[0] );
2196                                         $stripped = array_merge( $stripped, $m[1] );
2197                                 }
2198                         }
2199                 }
2200                 wfProfileOut( __METHOD__ );
2201                 return array($words, $stripped);
2202         }
2203
2204         function orig () {
2205                 wfProfileIn( __METHOD__ );
2206                 $orig = new _HWLDF_WordAccumulator;
2207
2208                 foreach ($this->edits as $edit) {
2209                         if ($edit->type == 'copy')
2210                         $orig->addWords($edit->orig);
2211                         elseif ($edit->orig)
2212                         $orig->addWords($edit->orig, 'del');
2213                 }
2214                 $lines = $orig->getLines();
2215                 wfProfileOut( __METHOD__ );
2216                 return $lines;
2217         }
2218
2219         function closing () {
2220                 wfProfileIn( __METHOD__ );
2221                 $closing = new _HWLDF_WordAccumulator;
2222
2223                 foreach ($this->edits as $edit) {
2224                         if ($edit->type == 'copy')
2225                         $closing->addWords($edit->closing);
2226                         elseif ($edit->closing)
2227                         $closing->addWords($edit->closing, 'ins');
2228                 }
2229                 $lines = $closing->getLines();
2230                 wfProfileOut( __METHOD__ );
2231                 return $lines;
2232         }
2233 }
2234
2235 /**
2236  * Wikipedia Table style diff formatter.
2237  * @todo document
2238  * @private
2239  * @ingroup DifferenceEngine
2240  */
2241 class TableDiffFormatter extends DiffFormatter {
2242         function TableDiffFormatter() {
2243                 $this->leading_context_lines = 2;
2244                 $this->trailing_context_lines = 2;
2245         }
2246
2247         public static function escapeWhiteSpace( $msg ) {
2248                 $msg = preg_replace( '/^ /m', '&nbsp; ', $msg );
2249                 $msg = preg_replace( '/ $/m', ' &nbsp;', $msg );
2250                 $msg = preg_replace( '/  /', '&nbsp; ', $msg );
2251                 return $msg;
2252         }
2253
2254         function _block_header( $xbeg, $xlen, $ybeg, $ylen ) {
2255                 $r = '<tr><td colspan="2" class="diff-lineno"><!--LINE '.$xbeg."--></td>\n" .
2256                   '<td colspan="2" class="diff-lineno"><!--LINE '.$ybeg."--></td></tr>\n";
2257                 return $r;
2258         }
2259
2260         function _start_block( $header ) {
2261                 echo $header;
2262         }
2263
2264         function _end_block() {
2265         }
2266
2267         function _lines( $lines, $prefix=' ', $color='white' ) {
2268         }
2269
2270         # HTML-escape parameter before calling this
2271         function addedLine( $line ) {
2272                 return $this->wrapLine( '+', 'diff-addedline', $line );
2273         }
2274
2275         # HTML-escape parameter before calling this
2276         function deletedLine( $line ) {
2277                 return $this->wrapLine( '-', 'diff-deletedline', $line );
2278         }
2279
2280         # HTML-escape parameter before calling this
2281         function contextLine( $line ) {
2282                 return $this->wrapLine( ' ', 'diff-context', $line );
2283         }
2284
2285         private function wrapLine( $marker, $class, $line ) {
2286                 if( $line !== '' ) {
2287                         // The <div> wrapper is needed for 'overflow: auto' style to scroll properly
2288                         $line = Xml::tags( 'div', null, $this->escapeWhiteSpace( $line ) );
2289                 }
2290                 return "<td class='diff-marker'>$marker</td><td class='$class'>$line</td>";
2291         }
2292
2293         function emptyLine() {
2294                 return '<td colspan="2">&nbsp;</td>';
2295         }
2296
2297         function _added( $lines ) {
2298                 foreach ($lines as $line) {
2299                         echo '<tr>' . $this->emptyLine() .
2300                         $this->addedLine( '<ins class="diffchange">' .
2301                         htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";
2302                 }
2303         }
2304
2305         function _deleted($lines) {
2306                 foreach ($lines as $line) {
2307                         echo '<tr>' . $this->deletedLine( '<del class="diffchange">' .
2308                         htmlspecialchars ( $line ) . '</del>' ) .
2309                         $this->emptyLine() . "</tr>\n";
2310                 }
2311         }
2312
2313         function _context( $lines ) {
2314                 foreach ($lines as $line) {
2315                         echo '<tr>' .
2316                         $this->contextLine( htmlspecialchars ( $line ) ) .
2317                         $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";
2318                 }
2319         }
2320
2321         function _changed( $orig, $closing ) {
2322                 wfProfileIn( __METHOD__ );
2323
2324                 $diff = new WordLevelDiff( $orig, $closing );
2325                 $del = $diff->orig();
2326                 $add = $diff->closing();
2327
2328                 # Notice that WordLevelDiff returns HTML-escaped output.
2329                 # Hence, we will be calling addedLine/deletedLine without HTML-escaping.
2330
2331                 while ( $line = array_shift( $del ) ) {
2332                         $aline = array_shift( $add );
2333                         echo '<tr>' . $this->deletedLine( $line ) .
2334                         $this->addedLine( $aline ) . "</tr>\n";
2335                 }
2336                 foreach ($add as $line) {       # If any leftovers
2337                         echo '<tr>' . $this->emptyLine() .
2338                         $this->addedLine( $line ) . "</tr>\n";
2339                 }
2340                 wfProfileOut( __METHOD__ );
2341         }
2342 }