includes/diff/DifferenceEngine.php

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