[Summary view] [Print] [Text view]

   1  <?php
   2  /** 
   3  *
   4  * @package phpBB3
   5  * @version $Id: diff.php,v 1.2 2006/09/02 13:33:05 acydburn Exp $
   6  * @copyright (c) 2006 phpBB Group 
   7  * @license http://opensource.org/licenses/gpl-license.php GNU Public License 
   8  *
   9  */
  10  
  11  /**
  12  */
  13  if (!defined('IN_PHPBB'))
  14  {
  15      exit;
  16  }
  17  
  18  // Include renderer and engine
  19  include_once($phpbb_root_path . 'includes/diff/engine.' . $phpEx);
  20  include_once($phpbb_root_path . 'includes/diff/renderer.' . $phpEx);
  21  
  22  /**
  23  * Code from pear.php.net, Text_Diff-0.2.1 (beta) package
  24  * http://pear.php.net/package/Text_Diff/
  25  *
  26  * Modified by Acyd Burn to meet our coding standards
  27  * and being able to integrate into phpBB
  28  */
  29  
  30  /**
  31  * General API for generating and formatting diffs - the differences between
  32  * two sequences of strings.
  33  *
  34  * The PHP diff code used in this package was originally written by Geoffrey
  35  * T. Dairiki and is used with his permission.
  36  *
  37  * @package phpBB3
  38  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  39  */
  40  class diff
  41  {
  42      /**
  43      * Array of changes.
  44      * @var array
  45      */
  46      var $_edits;
  47  
  48      /**
  49      * Computes diffs between sequences of strings.
  50      *
  51      * @param array $from_lines  An array of strings. Typically these are lines from a file.
  52      * @param array $to_lines    An array of strings.
  53      */
  54  	function diff($from_lines, $to_lines)
  55      {
  56          $diff_engine = &new diff_engine();
  57          $this->_edits = call_user_func_array(array($diff_engine, 'diff'), array($from_lines, $to_lines));
  58      }
  59  
  60      /**
  61      * Returns the array of differences.
  62      */
  63  	function get_diff()
  64      {
  65          return $this->_edits;
  66      }
  67  
  68      /**
  69      * Computes a reversed diff.
  70      *
  71      * Example:
  72      * <code>
  73      * $diff = &new diff($lines1, $lines2);
  74      * $rev = $diff->reverse();
  75      * </code>
  76      *
  77      * @return diff  A Diff object representing the inverse of the original diff.
  78      *               Note that we purposely don't return a reference here, since 
  79      *               this essentially is a clone() method.
  80      */
  81  	function reverse()
  82      {
  83          if (version_compare(zend_version(), '2', '>'))
  84          {
  85              $rev = clone($this);
  86          }
  87          else
  88          {
  89              $rev = $this;
  90          }
  91  
  92          $rev->_edits = array();
  93  
  94          foreach ($this->_edits as $edit)
  95          {
  96              $rev->_edits[] = $edit->reverse();
  97          }
  98  
  99          return $rev;
 100      }
 101  
 102      /**
 103      * Checks for an empty diff.
 104      *
 105      * @return boolean  True if two sequences were identical.
 106      */
 107  	function is_empty()
 108      {
 109          foreach ($this->_edits as $edit)
 110          {
 111              if (!is_a($edit, 'diff_op_copy'))
 112              {
 113                  return false;
 114              }
 115          }
 116          return true;
 117      }
 118  
 119      /**
 120      * Computes the length of the Longest Common Subsequence (LCS).
 121      *
 122      * This is mostly for diagnostic purposes.
 123      *
 124      * @return integer  The length of the LCS.
 125      */
 126  	function lcs()
 127      {
 128          $lcs = 0;
 129  
 130          foreach ($this->_edits as $edit)
 131          {
 132              if (is_a($edit, 'diff_op_copy'))
 133              {
 134                  $lcs += sizeof($edit->orig);
 135              }
 136          }
 137          return $lcs;
 138      }
 139  
 140      /**
 141      * Gets the original set of lines.
 142      *
 143      * This reconstructs the $from_lines parameter passed to the constructor.
 144      *
 145      * @return array  The original sequence of strings.
 146      */
 147  	function get_original()
 148      {
 149          $lines = array();
 150  
 151          foreach ($this->_edits as $edit)
 152          {
 153              if ($edit->orig)
 154              {
 155                  array_splice($lines, sizeof($lines), 0, $edit->orig);
 156              }
 157          }
 158          return $lines;
 159      }
 160  
 161      /**
 162      * Gets the final set of lines.
 163      *
 164      * This reconstructs the $to_lines parameter passed to the constructor.
 165      *
 166      * @return array  The sequence of strings.
 167      */
 168  	function get_final()
 169      {
 170          $lines = array();
 171  
 172          foreach ($this->_edits as $edit)
 173          {
 174              if ($edit->final)
 175              {
 176                  array_splice($lines, sizeof($lines), 0, $edit->final);
 177              }
 178          }
 179          return $lines;
 180      }
 181  
 182      /**
 183      * Removes trailing newlines from a line of text. This is meant to be used with array_walk().
 184      *
 185      * @param string $line  The line to trim.
 186      * @param integer $key  The index of the line in the array. Not used.
 187      */
 188  	function trim_newlines(&$line, $key)
 189      {
 190          $line = str_replace(array("\n", "\r"), '', $line);
 191      }
 192  
 193      /**
 194      * Checks a diff for validity.
 195      *
 196      * This is here only for debugging purposes.
 197      */
 198  	function _check($from_lines, $to_lines)
 199      {
 200          if (serialize($from_lines) != serialize($this->get_original()))
 201          {
 202              trigger_error("[diff] Reconstructed original doesn't match", E_USER_ERROR);
 203          }
 204  
 205          if (serialize($to_lines) != serialize($this->get_final()))
 206          {
 207              trigger_error("[diff] Reconstructed final doesn't match", E_USER_ERROR);
 208          }
 209  
 210          $rev = $this->reverse();
 211  
 212          if (serialize($to_lines) != serialize($rev->get_original()))
 213          {
 214              trigger_error("[diff] Reversed original doesn't match", E_USER_ERROR);
 215          }
 216  
 217          if (serialize($from_lines) != serialize($rev->get_final()))
 218          {
 219              trigger_error("[diff] Reversed final doesn't match", E_USER_ERROR);
 220          }
 221  
 222          $prevtype = null;
 223  
 224          foreach ($this->_edits as $edit)
 225          {
 226              if ($prevtype == get_class($edit))
 227              {
 228                  trigger_error("[diff] Edit sequence is non-optimal", E_USER_ERROR);
 229              }
 230              $prevtype = get_class($edit);
 231          }
 232  
 233          return true;
 234      }
 235  }
 236  
 237  /**
 238  * @package phpBB3
 239  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 240  */
 241  class mapped_diff extends diff
 242  {
 243      /**
 244      * Computes a diff between sequences of strings.
 245      *
 246      * This can be used to compute things like case-insensitve diffs, or diffs
 247      * which ignore changes in white-space.
 248      *
 249      * @param array $from_lines         An array of strings.
 250      * @param array $to_lines           An array of strings.
 251      * @param array $mapped_from_lines  This array should have the same size number of elements as $from_lines.
 252      *                                  The elements in $mapped_from_lines and $mapped_to_lines are what is actually
 253      *                                  compared when computing the diff.
 254      * @param array $mapped_to_lines    This array should have the same number of elements as $to_lines.
 255      */
 256  	function mapped_diff($from_lines, $to_lines, $mapped_from_lines, $mapped_to_lines)
 257      {
 258          if (sizeof($from_lines) != sizeof($mapped_from_lines) || sizeof($to_lines) != sizeof($mapped_to_lines))
 259          {
 260              return false;
 261          }
 262  
 263          parent::diff($mapped_from_lines, $mapped_to_lines);
 264  
 265          $xi = $yi = 0;
 266          for ($i = 0; $i < sizeof($this->_edits); $i++)
 267          {
 268              $orig = &$this->_edits[$i]->orig;
 269              if (is_array($orig))
 270              {
 271                  $orig = array_slice($from_lines, $xi, sizeof($orig));
 272                  $xi += sizeof($orig);
 273              }
 274  
 275              $final = &$this->_edits[$i]->final;
 276              if (is_array($final))
 277              {
 278                  $final = array_slice($to_lines, $yi, sizeof($final));
 279                  $yi += sizeof($final);
 280              }
 281          }
 282      }
 283  }
 284  
 285  /**
 286  * @package phpBB3
 287  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 288  *
 289  * @access private
 290  */
 291  class diff_op
 292  {
 293      var $orig;
 294      var $final;
 295  
 296  	function reverse()
 297      {
 298          trigger_error('[diff] Abstract method', E_USER_ERROR);
 299      }
 300  
 301  	function norig()
 302      {
 303          return ($this->orig) ? sizeof($this->orig) : 0;
 304      }
 305  
 306  	function nfinal()
 307      {
 308          return ($this->final) ? sizeof($this->final) : 0;
 309      }
 310  }
 311  
 312  /**
 313  * @package phpBB3
 314  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 315  *
 316  * @access private
 317  */
 318  class diff_op_copy extends diff_op
 319  {
 320  	function diff_op_copy($orig, $final = false)
 321      {
 322          if (!is_array($final))
 323          {
 324              $final = $orig;
 325          }
 326          $this->orig = $orig;
 327          $this->final = $final;
 328      }
 329  
 330      function &reverse()
 331      {
 332          $reverse = &new diff_op_copy($this->final, $this->orig);
 333          return $reverse;
 334      }
 335  }
 336  
 337  /**
 338  * @package phpBB3
 339  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 340  *
 341  * @access private
 342  */
 343  class diff_op_delete extends diff_op
 344  {
 345  	function diff_op_delete($lines)
 346      {
 347          $this->orig = $lines;
 348          $this->final = false;
 349      }
 350  
 351      function &reverse()
 352      {
 353          $reverse = &new diff_op_add($this->orig);
 354          return $reverse;
 355      }
 356  }
 357  
 358  /**
 359  * @package phpBB3
 360  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 361  *
 362  * @access private
 363  */
 364  class diff_op_add extends diff_op
 365  {
 366  	function diff_op_add($lines)
 367      {
 368          $this->final = $lines;
 369          $this->orig = false;
 370      }
 371  
 372      function &reverse()
 373      {
 374          $reverse = &new diff_op_delete($this->final);
 375          return $reverse;
 376      }
 377  }
 378  
 379  /**
 380  * @package phpBB3
 381  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 382  *
 383  * @access private
 384  */
 385  class diff_op_change extends diff_op
 386  {
 387  	function diff_op_change($orig, $final)
 388      {
 389          $this->orig = $orig;
 390          $this->final = $final;
 391      }
 392  
 393      function &reverse()
 394      {
 395          $reverse = &new diff_op_change($this->final, $this->orig);
 396          return $reverse;
 397      }
 398  }
 399  
 400  
 401  /**
 402  * A class for computing three way diffs.
 403  *
 404  * @package phpBB3
 405  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 406  */
 407  class diff3 extends diff
 408  {
 409      /**
 410      * Conflict counter.
 411      * @var integer
 412      */
 413      var $_conflicting_blocks = 0;
 414  
 415      /**
 416      * Computes diff between 3 sequences of strings.
 417      *
 418      * @param array $orig    The original lines to use.
 419      * @param array $final1  The first version to compare to.
 420      * @param array $final2  The second version to compare to.
 421      */
 422  	function diff3($orig, $final1, $final2)
 423      {
 424          $engine = new diff_engine();
 425          $this->_edits = $this->_diff3($engine->diff($orig, $final1), $engine->diff($orig, $final2));
 426      }
 427  
 428      /**
 429      * Return merged output
 430      *
 431      * @param string $label1 the cvs file version/label from the original set of lines
 432      * @param string $label2 the cvs file version/label from the new set of lines
 433      * @param string $label_sep the explanation between label1 and label2 - more of a helper for the user
 434      * @param bool $get_conflicts if set to true only the number of conflicts is returned
 435      * @param bool $merge_new if set to true the merged output will have the new file contents on a conflicting merge
 436      *
 437      * @return mixed the merged output
 438      */
 439  	function merged_output($label1 = 'CURRENT_FILE', $label2 = 'NEW_FILE', $label_sep = 'DIFF_SEP_EXPLAIN', $get_conflicts = false, $merge_new = false)
 440      {
 441          global $user;
 442  
 443          if ($get_conflicts)
 444          {
 445              foreach ($this->_edits as $edit)
 446              {
 447                  if ($edit->is_conflict())
 448                  {
 449                      $this->_conflicting_blocks++;
 450                  }
 451              }
 452  
 453              return $this->_conflicting_blocks;
 454          }
 455  
 456          $label1 = (!empty($user->lang[$label1])) ? $user->lang[$label1] : $label1;
 457          $label2 = (!empty($user->lang[$label2])) ? $user->lang[$label2] : $label2;
 458          $label_sep = (!empty($user->lang[$label_sep])) ? $user->lang[$label_sep] : $label_sep;
 459  
 460          $lines = array();
 461  
 462          foreach ($this->_edits as $edit)
 463          {
 464              if ($edit->is_conflict())
 465              {
 466                  if (!$merge_new)
 467                  {
 468                      $lines = array_merge($lines, array('<<<<<<<' . ($label1 ? ' ' . $label1 : '')), $edit->final1, array('=======' . ($label_sep ? ' ' . $label_sep : '')), $edit->final2, array('>>>>>>>' . ($label2 ? ' ' . $label2 : '')));
 469                  }
 470                  else
 471                  {
 472                      $lines = array_merge($lines, $edit->final1);
 473                  }
 474                  $this->_conflicting_blocks++;
 475              }
 476              else
 477              {
 478                  $lines = array_merge($lines, $edit->merged());
 479              }
 480          }
 481  
 482          return $lines;
 483      }
 484  
 485      /**
 486      * Merge the output and use the new file code for conflicts
 487      */
 488  	function merged_new_output()
 489      {
 490          $lines = array();
 491  
 492          foreach ($this->_edits as $edit)
 493          {
 494              if ($edit->is_conflict())
 495              {
 496                  $lines = array_merge($lines, $edit->final2);
 497              }
 498              else
 499              {
 500                  $lines = array_merge($lines, $edit->merged());
 501              }
 502          }
 503  
 504          return $lines;
 505      }
 506  
 507      /**
 508      * Merge the output and use the original file code for conflicts
 509      */
 510  	function merged_orig_output()
 511      {
 512          $lines = array();
 513  
 514          foreach ($this->_edits as $edit)
 515          {
 516              if ($edit->is_conflict())
 517              {
 518                  $lines = array_merge($lines, $edit->final1);
 519              }
 520              else
 521              {
 522                  $lines = array_merge($lines, $edit->merged());
 523              }
 524          }
 525  
 526          return $lines;
 527      }
 528  
 529      /**
 530      * Get conflicting block(s)
 531      */
 532  	function get_conflicts()
 533      {
 534          $conflicts = array();
 535  
 536          foreach ($this->_edits as $edit)
 537          {
 538              if ($edit->is_conflict())
 539              {
 540                  $conflicts[] = array($edit->final1, $edit->final2);
 541              }
 542          }
 543  
 544          return $conflicts;
 545      }
 546  
 547      /**
 548      * @access private
 549      */
 550  	function _diff3($edits1, $edits2)
 551      {
 552          $edits = array();
 553          $bb = &new diff3_block_builder();
 554  
 555          $e1 = current($edits1);
 556          $e2 = current($edits2);
 557  
 558          while ($e1 || $e2)
 559          {
 560              if ($e1 && $e2 && is_a($e1, 'diff_op_copy') && is_a($e2, 'diff_op_copy'))
 561              {
 562                  // We have copy blocks from both diffs. This is the (only) time we want to emit a diff3 copy block.
 563                  // Flush current diff3 diff block, if any.
 564                  if ($edit = $bb->finish())
 565                  {
 566                      $edits[] = $edit;
 567                  }
 568  
 569                  $ncopy = min($e1->norig(), $e2->norig());
 570                  $edits[] = &new diff3_op_copy(array_slice($e1->orig, 0, $ncopy));
 571  
 572                  if ($e1->norig() > $ncopy)
 573                  {
 574                      array_splice($e1->orig, 0, $ncopy);
 575                      array_splice($e1->final, 0, $ncopy);
 576                  }
 577                  else
 578                  {
 579                      $e1 = next($edits1);
 580                  }
 581  
 582                  if ($e2->norig() > $ncopy)
 583                  {
 584                      array_splice($e2->orig, 0, $ncopy);
 585                      array_splice($e2->final, 0, $ncopy);
 586                  }
 587                  else
 588                  {
 589                      $e2 = next($edits2);
 590                  }
 591              }
 592              else
 593              {
 594                  if ($e1 && $e2)
 595                  {
 596                      if ($e1->orig && $e2->orig)
 597                      {
 598                          $norig = min($e1->norig(), $e2->norig());
 599                          $orig = array_splice($e1->orig, 0, $norig);
 600                          array_splice($e2->orig, 0, $norig);
 601                          $bb->input($orig);
 602                      }
 603                      else
 604                      {
 605                          $norig = 0;
 606                      }
 607  
 608                      if (is_a($e1, 'diff_op_copy'))
 609                      {
 610                          $bb->out1(array_splice($e1->final, 0, $norig));
 611                      }
 612  
 613                      if (is_a($e2, 'diff_op_copy'))
 614                      {
 615                          $bb->out2(array_splice($e2->final, 0, $norig));
 616                      }
 617                  }
 618  
 619                  if ($e1 && ! $e1->orig)
 620                  {
 621                      $bb->out1($e1->final);
 622                      $e1 = next($edits1);
 623                  }
 624  
 625                  if ($e2 && ! $e2->orig)
 626                  {
 627                      $bb->out2($e2->final);
 628                      $e2 = next($edits2);
 629                  }
 630              }
 631          }
 632  
 633          if ($edit = $bb->finish())
 634          {
 635              $edits[] = $edit;
 636          }
 637  
 638          return $edits;
 639      }
 640  }
 641  
 642  /**
 643  * @package phpBB3
 644  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 645  *
 646  * @access private
 647  */
 648  class diff3_op
 649  {
 650  	function diff3_op($orig = false, $final1 = false, $final2 = false)
 651      {
 652          $this->orig = $orig ? $orig : array();
 653          $this->final1 = $final1 ? $final1 : array();
 654          $this->final2 = $final2 ? $final2 : array();
 655      }
 656  
 657  	function merged()
 658      {
 659          if (!isset($this->_merged))
 660          {
 661              if ($this->final1 === $this->final2)
 662              {
 663                  $this->_merged = &$this->final1;
 664              }
 665              else if ($this->final1 === $this->orig)
 666              {
 667                  $this->_merged = &$this->final2;
 668              }
 669              else if ($this->final2 === $this->orig)
 670              {
 671                  $this->_merged = &$this->final1;
 672              }
 673              else
 674              {
 675                  $this->_merged = false;
 676              }
 677          }
 678  
 679          return $this->_merged;
 680      }
 681  
 682  	function is_conflict()
 683      {
 684          return ($this->merged() === false) ? true : false;
 685      }
 686  }
 687  
 688  /**
 689  * @package phpBB3
 690  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 691  *
 692  * @access private
 693  */
 694  class diff3_op_copy extends diff3_op
 695  {
 696  	function diff3_op_copy($lines = false)
 697      {
 698          $this->orig = $lines ? $lines : array();
 699          $this->final1 = &$this->orig;
 700          $this->final2 = &$this->orig;
 701      }
 702  
 703  	function merged()
 704      {
 705          return $this->orig;
 706      }
 707  
 708  	function is_conflict()
 709      {
 710          return false;
 711      }
 712  }
 713  
 714  /**
 715  * @package phpBB3
 716  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 717  *
 718  * @access private
 719  */
 720  class diff3_block_builder
 721  {
 722  	function diff3_block_builder()
 723      {
 724          $this->_init();
 725      }
 726  
 727  	function input($lines)
 728      {
 729          if ($lines)
 730          {
 731              $this->_append($this->orig, $lines);
 732          }
 733      }
 734  
 735  	function out1($lines)
 736      {
 737          if ($lines)
 738          {
 739              $this->_append($this->final1, $lines);
 740          }
 741      }
 742  
 743  	function out2($lines)
 744      {
 745          if ($lines)
 746          {
 747              $this->_append($this->final2, $lines);
 748          }
 749      }
 750  
 751  	function is_empty()
 752      {
 753          return !$this->orig && !$this->final1 && !$this->final2;
 754      }
 755  
 756  	function finish()
 757      {
 758          if ($this->is_empty())
 759          {
 760              return false;
 761          }
 762          else
 763          {
 764              $edit = &new diff3_op($this->orig, $this->final1, $this->final2);
 765              $this->_init();
 766              return $edit;
 767          }
 768      }
 769  
 770  	function _init()
 771      {
 772          $this->orig = $this->final1 = $this->final2 = array();
 773      }
 774  
 775  	function _append(&$array, $lines)
 776      {
 777          array_splice($array, sizeof($array), 0, $lines);
 778      }
 779  }
 780  
 781  ?>