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