[Summary view] [Print] [Text view]

   1  <?php
   2  /**
   3  *
   4  * This file is part of the phpBB Forum Software package.
   5  *
   6  * @copyright (c) phpBB Limited <https://www.phpbb.com>
   7  * @license GNU General Public License, version 2 (GPL-2.0)
   8  *
   9  * For full copyright and license information, please see
  10  * the docs/CREDITS.txt file.
  11  *
  12  */
  13  
  14  /**
  15  * @ignore
  16  */
  17  if (!defined('IN_PHPBB'))
  18  {
  19      exit;
  20  }
  21  
  22  /**
  23  * Code from pear.php.net, Text_Diff-1.1.0 package
  24  * http://pear.php.net/package/Text_Diff/
  25  *
  26  * Modified by phpBB Limited to meet our coding standards
  27  * and being able to integrate into phpBB
  28  *
  29  * General API for generating and formatting diffs - the differences between
  30  * two sequences of strings.
  31  *
  32  * Copyright 2004 Geoffrey T. Dairiki <dairiki@dairiki.org>
  33  * Copyright 2004-2008 The Horde Project (http://www.horde.org/)
  34  *
  35  * @package diff
  36  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  37  */
  38  class diff
  39  {
  40      /**
  41      * Array of changes.
  42      * @var array
  43      */
  44      var $_edits;
  45  
  46      /**
  47      * Computes diffs between sequences of strings.
  48      *
  49      * @param array    &$from_content    An array of strings. Typically these are lines from a file.
  50      * @param array    &$to_content    An array of strings.
  51      * @param bool    $preserve_cr    If true, \r is replaced by a new line in the diff output
  52      */
  53  	function diff(&$from_content, &$to_content, $preserve_cr = true)
  54      {
  55          $diff_engine = new diff_engine();
  56          $this->_edits = $diff_engine->diff($from_content, $to_content, $preserve_cr);
  57      }
  58  
  59      /**
  60      * Returns the array of differences.
  61      */
  62  	function get_diff()
  63      {
  64          return $this->_edits;
  65      }
  66  
  67      /**
  68      * returns the number of new (added) lines in a given diff.
  69      *
  70      * @since Text_Diff 1.1.0
  71      *
  72      * @return integer The number of new lines
  73      */
  74  	function count_added_lines()
  75      {
  76          $count = 0;
  77  
  78          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
  79          {
  80              $edit = $this->_edits[$i];
  81  
  82              if (is_a($edit, 'diff_op_add') || is_a($edit, 'diff_op_change'))
  83              {
  84                  $count += $edit->nfinal();
  85              }
  86          }
  87          return $count;
  88      }
  89  
  90      /**
  91      * Returns the number of deleted (removed) lines in a given diff.
  92      *
  93      * @since Text_Diff 1.1.0
  94      *
  95      * @return integer The number of deleted lines
  96      */
  97  	function count_deleted_lines()
  98      {
  99          $count = 0;
 100  
 101          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 102          {
 103              $edit = $this->_edits[$i];
 104  
 105              if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_change'))
 106              {
 107                  $count += $edit->norig();
 108              }
 109          }
 110          return $count;
 111      }
 112  
 113      /**
 114      * Computes a reversed diff.
 115      *
 116      * Example:
 117      * <code>
 118      * $diff = new diff($lines1, $lines2);
 119      * $rev = $diff->reverse();
 120      * </code>
 121      *
 122      * @return diff  A Diff object representing the inverse of the original diff.
 123      *               Note that we purposely don't return a reference here, since
 124      *               this essentially is a clone() method.
 125      */
 126  	function reverse()
 127      {
 128          if (version_compare(zend_version(), '2', '>'))
 129          {
 130              $rev = clone($this);
 131          }
 132          else
 133          {
 134              $rev = $this;
 135          }
 136  
 137          $rev->_edits = array();
 138  
 139          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 140          {
 141              $edit = $this->_edits[$i];
 142              $rev->_edits[] = $edit->reverse();
 143          }
 144  
 145          return $rev;
 146      }
 147  
 148      /**
 149      * Checks for an empty diff.
 150      *
 151      * @return boolean  True if two sequences were identical.
 152      */
 153  	function is_empty()
 154      {
 155          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 156          {
 157              $edit = $this->_edits[$i];
 158  
 159              // skip diff_op_copy
 160              if (is_a($edit, 'diff_op_copy'))
 161              {
 162                  continue;
 163              }
 164  
 165              if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_add'))
 166              {
 167                  $orig = $edit->orig;
 168                  $final = $edit->final;
 169  
 170                  // We can simplify one case where the array is usually supposed to be empty...
 171                  if (sizeof($orig) == 1 && trim($orig[0]) === '') $orig = array();
 172                  if (sizeof($final) == 1 && trim($final[0]) === '') $final = array();
 173  
 174                  if (!$orig && !$final)
 175                  {
 176                      continue;
 177                  }
 178  
 179                  return false;
 180              }
 181  
 182              return false;
 183          }
 184  
 185          return true;
 186      }
 187  
 188      /**
 189      * Computes the length of the Longest Common Subsequence (LCS).
 190      *
 191      * This is mostly for diagnostic purposes.
 192      *
 193      * @return integer  The length of the LCS.
 194      */
 195  	function lcs()
 196      {
 197          $lcs = 0;
 198  
 199          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 200          {
 201              $edit = $this->_edits[$i];
 202  
 203              if (is_a($edit, 'diff_op_copy'))
 204              {
 205                  $lcs += sizeof($edit->orig);
 206              }
 207          }
 208          return $lcs;
 209      }
 210  
 211      /**
 212      * Gets the original set of lines.
 213      *
 214      * This reconstructs the $from_lines parameter passed to the constructor.
 215      *
 216      * @return array  The original sequence of strings.
 217      */
 218  	function get_original()
 219      {
 220          $lines = array();
 221  
 222          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 223          {
 224              $edit = $this->_edits[$i];
 225  
 226              if ($edit->orig)
 227              {
 228                  array_splice($lines, sizeof($lines), 0, $edit->orig);
 229              }
 230          }
 231          return $lines;
 232      }
 233  
 234      /**
 235      * Gets the final set of lines.
 236      *
 237      * This reconstructs the $to_lines parameter passed to the constructor.
 238      *
 239      * @return array  The sequence of strings.
 240      */
 241  	function get_final()
 242      {
 243          $lines = array();
 244  
 245          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 246          {
 247              $edit = $this->_edits[$i];
 248  
 249              if ($edit->final)
 250              {
 251                  array_splice($lines, sizeof($lines), 0, $edit->final);
 252              }
 253          }
 254          return $lines;
 255      }
 256  
 257      /**
 258      * Removes trailing newlines from a line of text. This is meant to be used with array_walk().
 259      *
 260      * @param string &$line  The line to trim.
 261      * @param integer $key  The index of the line in the array. Not used.
 262      */
 263  	function trim_newlines(&$line, $key)
 264      {
 265          $line = str_replace(array("\n", "\r"), '', $line);
 266      }
 267  
 268      /**
 269      * Checks a diff for validity.
 270      *
 271      * This is here only for debugging purposes.
 272      */
 273  	function _check($from_lines, $to_lines)
 274      {
 275          if (serialize($from_lines) != serialize($this->get_original()))
 276          {
 277              trigger_error("[diff] Reconstructed original doesn't match", E_USER_ERROR);
 278          }
 279  
 280          if (serialize($to_lines) != serialize($this->get_final()))
 281          {
 282              trigger_error("[diff] Reconstructed final doesn't match", E_USER_ERROR);
 283          }
 284  
 285          $rev = $this->reverse();
 286  
 287          if (serialize($to_lines) != serialize($rev->get_original()))
 288          {
 289              trigger_error("[diff] Reversed original doesn't match", E_USER_ERROR);
 290          }
 291  
 292          if (serialize($from_lines) != serialize($rev->get_final()))
 293          {
 294              trigger_error("[diff] Reversed final doesn't match", E_USER_ERROR);
 295          }
 296  
 297          $prevtype = null;
 298  
 299          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 300          {
 301              $edit = $this->_edits[$i];
 302  
 303              if ($prevtype == get_class($edit))
 304              {
 305                  trigger_error("[diff] Edit sequence is non-optimal", E_USER_ERROR);
 306              }
 307              $prevtype = get_class($edit);
 308          }
 309  
 310          return true;
 311      }
 312  }
 313  
 314  /**
 315  * @package diff
 316  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 317  */
 318  class mapped_diff extends diff
 319  {
 320      /**
 321      * Computes a diff between sequences of strings.
 322      *
 323      * This can be used to compute things like case-insensitve diffs, or diffs
 324      * which ignore changes in white-space.
 325      *
 326      * @param array $from_lines         An array of strings.
 327      * @param array $to_lines           An array of strings.
 328      * @param array $mapped_from_lines  This array should have the same size number of elements as $from_lines.
 329      *                                  The elements in $mapped_from_lines and $mapped_to_lines are what is actually
 330      *                                  compared when computing the diff.
 331      * @param array $mapped_to_lines    This array should have the same number of elements as $to_lines.
 332      */
 333  	function mapped_diff(&$from_lines, &$to_lines, &$mapped_from_lines, &$mapped_to_lines)
 334      {
 335          if (sizeof($from_lines) != sizeof($mapped_from_lines) || sizeof($to_lines) != sizeof($mapped_to_lines))
 336          {
 337              return false;
 338          }
 339  
 340          parent::diff($mapped_from_lines, $mapped_to_lines);
 341  
 342          $xi = $yi = 0;
 343          for ($i = 0; $i < sizeof($this->_edits); $i++)
 344          {
 345              $orig = &$this->_edits[$i]->orig;
 346              if (is_array($orig))
 347              {
 348                  $orig = array_slice($from_lines, $xi, sizeof($orig));
 349                  $xi += sizeof($orig);
 350              }
 351  
 352              $final = &$this->_edits[$i]->final;
 353              if (is_array($final))
 354              {
 355                  $final = array_slice($to_lines, $yi, sizeof($final));
 356                  $yi += sizeof($final);
 357              }
 358          }
 359      }
 360  }
 361  
 362  /**
 363  * @package diff
 364  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 365  *
 366  * @access private
 367  */
 368  class diff_op
 369  {
 370      var $orig;
 371      var $final;
 372  
 373      function &reverse()
 374      {
 375          trigger_error('[diff] Abstract method', E_USER_ERROR);
 376      }
 377  
 378  	function norig()
 379      {
 380          return ($this->orig) ? sizeof($this->orig) : 0;
 381      }
 382  
 383  	function nfinal()
 384      {
 385          return ($this->final) ? sizeof($this->final) : 0;
 386      }
 387  }
 388  
 389  /**
 390  * @package diff
 391  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 392  *
 393  * @access private
 394  */
 395  class diff_op_copy extends diff_op
 396  {
 397  	function diff_op_copy($orig, $final = false)
 398      {
 399          if (!is_array($final))
 400          {
 401              $final = $orig;
 402          }
 403          $this->orig = $orig;
 404          $this->final = $final;
 405      }
 406  
 407      function &reverse()
 408      {
 409          $reverse = new diff_op_copy($this->final, $this->orig);
 410          return $reverse;
 411      }
 412  }
 413  
 414  /**
 415  * @package diff
 416  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 417  *
 418  * @access private
 419  */
 420  class diff_op_delete extends diff_op
 421  {
 422  	function diff_op_delete($lines)
 423      {
 424          $this->orig = $lines;
 425          $this->final = false;
 426      }
 427  
 428      function &reverse()
 429      {
 430          $reverse = new diff_op_add($this->orig);
 431          return $reverse;
 432      }
 433  }
 434  
 435  /**
 436  * @package diff
 437  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 438  *
 439  * @access private
 440  */
 441  class diff_op_add extends diff_op
 442  {
 443  	function diff_op_add($lines)
 444      {
 445          $this->final = $lines;
 446          $this->orig = false;
 447      }
 448  
 449      function &reverse()
 450      {
 451          $reverse = new diff_op_delete($this->final);
 452          return $reverse;
 453      }
 454  }
 455  
 456  /**
 457  * @package diff
 458  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 459  *
 460  * @access private
 461  */
 462  class diff_op_change extends diff_op
 463  {
 464  	function diff_op_change($orig, $final)
 465      {
 466          $this->orig = $orig;
 467          $this->final = $final;
 468      }
 469  
 470      function &reverse()
 471      {
 472          $reverse = new diff_op_change($this->final, $this->orig);
 473          return $reverse;
 474      }
 475  }
 476  
 477  
 478  /**
 479  * A class for computing three way diffs.
 480  *
 481  * @package diff
 482  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 483  */
 484  class diff3 extends diff
 485  {
 486      /**
 487      * Conflict counter.
 488      * @var integer
 489      */
 490      var $_conflicting_blocks = 0;
 491  
 492      /**
 493      * Computes diff between 3 sequences of strings.
 494      *
 495      * @param array &$orig        The original lines to use.
 496      * @param array &$final1        The first version to compare to.
 497      * @param array &$final2        The second version to compare to.
 498      * @param bool $preserve_cr    If true, \r\n and bare \r are replaced by a new line
 499      *                            in the diff output
 500      */
 501  	function diff3(&$orig, &$final1, &$final2, $preserve_cr = true)
 502      {
 503          $diff_engine = new diff_engine();
 504  
 505          $diff_1 = $diff_engine->diff($orig, $final1, $preserve_cr);
 506          $diff_2 = $diff_engine->diff($orig, $final2, $preserve_cr);
 507  
 508          unset($diff_engine);
 509  
 510          $this->_edits = $this->_diff3($diff_1, $diff_2);
 511      }
 512  
 513      /**
 514      * Return number of conflicts
 515      */
 516  	function get_num_conflicts()
 517      {
 518          $conflicts = 0;
 519  
 520          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 521          {
 522              $edit = $this->_edits[$i];
 523  
 524              if ($edit->is_conflict())
 525              {
 526                  $conflicts++;
 527              }
 528          }
 529  
 530          return $conflicts;
 531      }
 532  
 533      /**
 534      * Get conflicts content for download. This is generally a merged file, but preserving conflicts and adding explanations to it.
 535      * A user could then go through this file, search for the conflicts and changes the code accordingly.
 536      *
 537      * @param string $label1 the cvs file version/label from the original set of lines
 538      * @param string $label2 the cvs file version/label from the new set of lines
 539      * @param string $label_sep the explanation between label1 and label2 - more of a helper for the user
 540      *
 541      * @return mixed the merged output
 542      */
 543  	function get_conflicts_content($label1 = 'CURRENT_FILE', $label2 = 'NEW_FILE', $label_sep = 'DIFF_SEP_EXPLAIN')
 544      {
 545          global $user;
 546  
 547          $label1 = (!empty($user->lang[$label1])) ? $user->lang[$label1] : $label1;
 548          $label2 = (!empty($user->lang[$label2])) ? $user->lang[$label2] : $label2;
 549          $label_sep = (!empty($user->lang[$label_sep])) ? $user->lang[$label_sep] : $label_sep;
 550  
 551          $lines = array();
 552  
 553          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 554          {
 555              $edit = $this->_edits[$i];
 556  
 557              if ($edit->is_conflict())
 558              {
 559                  // Start conflict label
 560                  $label_start    = array('<<<<<<< ' . $label1);
 561                  $label_mid        = array('======= ' . $label_sep);
 562                  $label_end        = array('>>>>>>> ' . $label2);
 563  
 564                  $lines = array_merge($lines, $label_start, $edit->final1, $label_mid, $edit->final2, $label_end);
 565                  $this->_conflicting_blocks++;
 566              }
 567              else
 568              {
 569                  $lines = array_merge($lines, $edit->merged());
 570              }
 571          }
 572  
 573          return $lines;
 574      }
 575  
 576      /**
 577      * Return merged output (used by the renderer)
 578      *
 579      * @return mixed the merged output
 580      */
 581  	function merged_output()
 582      {
 583          return $this->get_conflicts_content();
 584      }
 585  
 586      /**
 587      * Merge the output and use the new file code for conflicts
 588      */
 589  	function merged_new_output()
 590      {
 591          $lines = array();
 592  
 593          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 594          {
 595              $edit = $this->_edits[$i];
 596  
 597              if ($edit->is_conflict())
 598              {
 599                  $lines = array_merge($lines, $edit->final2);
 600              }
 601              else
 602              {
 603                  $lines = array_merge($lines, $edit->merged());
 604              }
 605          }
 606  
 607          return $lines;
 608      }
 609  
 610      /**
 611      * Merge the output and use the original file code for conflicts
 612      */
 613  	function merged_orig_output()
 614      {
 615          $lines = array();
 616  
 617          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 618          {
 619              $edit = $this->_edits[$i];
 620  
 621              if ($edit->is_conflict())
 622              {
 623                  $lines = array_merge($lines, $edit->final1);
 624              }
 625              else
 626              {
 627                  $lines = array_merge($lines, $edit->merged());
 628              }
 629          }
 630  
 631          return $lines;
 632      }
 633  
 634      /**
 635      * Get conflicting block(s)
 636      */
 637  	function get_conflicts()
 638      {
 639          $conflicts = array();
 640  
 641          for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 642          {
 643              $edit = $this->_edits[$i];
 644  
 645              if ($edit->is_conflict())
 646              {
 647                  $conflicts[] = array($edit->final1, $edit->final2);
 648              }
 649          }
 650  
 651          return $conflicts;
 652      }
 653  
 654      /**
 655      * @access private
 656      */
 657  	function _diff3(&$edits1, &$edits2)
 658      {
 659          $edits = array();
 660          $bb = new diff3_block_builder();
 661  
 662          $e1 = current($edits1);
 663          $e2 = current($edits2);
 664  
 665          while ($e1 || $e2)
 666          {
 667              if ($e1 && $e2 && is_a($e1, 'diff_op_copy') && is_a($e2, 'diff_op_copy'))
 668              {
 669                  // We have copy blocks from both diffs. This is the (only) time we want to emit a diff3 copy block.
 670                  // Flush current diff3 diff block, if any.
 671                  if ($edit = $bb->finish())
 672                  {
 673                      $edits[] = $edit;
 674                  }
 675  
 676                  $ncopy = min($e1->norig(), $e2->norig());
 677                  $edits[] = new diff3_op_copy(array_slice($e1->orig, 0, $ncopy));
 678  
 679                  if ($e1->norig() > $ncopy)
 680                  {
 681                      array_splice($e1->orig, 0, $ncopy);
 682                      array_splice($e1->final, 0, $ncopy);
 683                  }
 684                  else
 685                  {
 686                      $e1 = next($edits1);
 687                  }
 688  
 689                  if ($e2->norig() > $ncopy)
 690                  {
 691                      array_splice($e2->orig, 0, $ncopy);
 692                      array_splice($e2->final, 0, $ncopy);
 693                  }
 694                  else
 695                  {
 696                      $e2 = next($edits2);
 697                  }
 698              }
 699              else
 700              {
 701                  if ($e1 && $e2)
 702                  {
 703                      if ($e1->orig && $e2->orig)
 704                      {
 705                          $norig = min($e1->norig(), $e2->norig());
 706                          $orig = array_splice($e1->orig, 0, $norig);
 707                          array_splice($e2->orig, 0, $norig);
 708                          $bb->input($orig);
 709                      }
 710                      else
 711                      {
 712                          $norig = 0;
 713                      }
 714  
 715                      if (is_a($e1, 'diff_op_copy'))
 716                      {
 717                          $bb->out1(array_splice($e1->final, 0, $norig));
 718                      }
 719  
 720                      if (is_a($e2, 'diff_op_copy'))
 721                      {
 722                          $bb->out2(array_splice($e2->final, 0, $norig));
 723                      }
 724                  }
 725  
 726                  if ($e1 && ! $e1->orig)
 727                  {
 728                      $bb->out1($e1->final);
 729                      $e1 = next($edits1);
 730                  }
 731  
 732                  if ($e2 && ! $e2->orig)
 733                  {
 734                      $bb->out2($e2->final);
 735                      $e2 = next($edits2);
 736                  }
 737              }
 738          }
 739  
 740          if ($edit = $bb->finish())
 741          {
 742              $edits[] = $edit;
 743          }
 744  
 745          return $edits;
 746      }
 747  }
 748  
 749  /**
 750  * @package diff
 751  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 752  *
 753  * @access private
 754  */
 755  class diff3_op
 756  {
 757  	function diff3_op($orig = false, $final1 = false, $final2 = false)
 758      {
 759          $this->orig = $orig ? $orig : array();
 760          $this->final1 = $final1 ? $final1 : array();
 761          $this->final2 = $final2 ? $final2 : array();
 762      }
 763  
 764  	function merged()
 765      {
 766          if (!isset($this->_merged))
 767          {
 768              // Prepare the arrays before we compare them. ;)
 769              $this->solve_prepare();
 770  
 771              if ($this->final1 === $this->final2)
 772              {
 773                  $this->_merged = &$this->final1;
 774              }
 775              else if ($this->final1 === $this->orig)
 776              {
 777                  $this->_merged = &$this->final2;
 778              }
 779              else if ($this->final2 === $this->orig)
 780              {
 781                  $this->_merged = &$this->final1;
 782              }
 783              else
 784              {
 785                  // The following tries to aggressively solve conflicts...
 786                  $this->_merged = false;
 787                  $this->solve_conflict();
 788              }
 789          }
 790  
 791          return $this->_merged;
 792      }
 793  
 794  	function is_conflict()
 795      {
 796          return ($this->merged() === false) ? true : false;
 797      }
 798  
 799      /**
 800      * Function to prepare the arrays for comparing - we want to skip over newline changes
 801      * @author acydburn
 802      */
 803  	function solve_prepare()
 804      {
 805          // We can simplify one case where the array is usually supposed to be empty...
 806          if (sizeof($this->orig) == 1 && trim($this->orig[0]) === '') $this->orig = array();
 807          if (sizeof($this->final1) == 1 && trim($this->final1[0]) === '') $this->final1 = array();
 808          if (sizeof($this->final2) == 1 && trim($this->final2[0]) === '') $this->final2 = array();
 809  
 810          // Now we only can have the case where the only difference between arrays are newlines, so compare all cases
 811  
 812          // First, some strings we can compare...
 813          $orig = $final1 = $final2 = '';
 814  
 815          foreach ($this->orig as $null => $line) $orig .= trim($line);
 816          foreach ($this->final1 as $null => $line) $final1 .= trim($line);
 817          foreach ($this->final2 as $null => $line) $final2 .= trim($line);
 818  
 819          // final1 === final2
 820          if ($final1 === $final2)
 821          {
 822              // We preserve the part which will be used in the merge later
 823              $this->final2 = $this->final1;
 824          }
 825          // final1 === orig
 826          else if ($final1 === $orig)
 827          {
 828              // Here it does not really matter what we choose, but we will use the new code
 829              $this->orig = $this->final1;
 830          }
 831          // final2 === orig
 832          else if ($final2 === $orig)
 833          {
 834              // Here it does not really matter too (final1 will be used), but we will use the new code
 835              $this->orig = $this->final2;
 836          }
 837      }
 838  
 839      /**
 840      * Find code portions from $orig in $final1 and use $final2 as merged instance if provided
 841      * @author acydburn
 842      */
 843  	function _compare_conflict_seq($orig, $final1, $final2 = false)
 844      {
 845          $result = array('merge_found' => false, 'merge' => array());
 846  
 847          $_orig = &$this->$orig;
 848          $_final1 = &$this->$final1;
 849  
 850          // Ok, we basically search for $orig in $final1
 851          $compare_seq = sizeof($_orig);
 852  
 853          // Go through the conflict code
 854          for ($i = 0, $j = 0, $size = sizeof($_final1); $i < $size; $i++, $j = $i)
 855          {
 856              $line = $_final1[$i];
 857              $skip = 0;
 858  
 859              for ($x = 0; $x < $compare_seq; $x++)
 860              {
 861                  // Try to skip all matching lines
 862                  if (trim($line) === trim($_orig[$x]))
 863                  {
 864                      $line = (++$j < $size) ? $_final1[$j] : $line;
 865                      $skip++;
 866                  }
 867              }
 868  
 869              if ($skip === $compare_seq)
 870              {
 871                  $result['merge_found'] = true;
 872  
 873                  if ($final2 !== false)
 874                  {
 875                      $result['merge'] = array_merge($result['merge'], $this->$final2);
 876                  }
 877                  $i += ($skip - 1);
 878              }
 879              else if ($final2 !== false)
 880              {
 881                  $result['merge'][] = $line;
 882              }
 883          }
 884  
 885          return $result;
 886      }
 887  
 888      /**
 889      * Tries to solve conflicts aggressively based on typical "assumptions"
 890      * @author acydburn
 891      */
 892  	function solve_conflict()
 893      {
 894          $this->_merged = false;
 895  
 896          // CASE ONE: orig changed into final2, but modified/unknown code in final1.
 897          // IF orig is found "as is" in final1 we replace the code directly in final1 and populate this as final2/merge
 898          if (sizeof($this->orig) && sizeof($this->final2))
 899          {
 900              $result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
 901  
 902              if ($result['merge_found'])
 903              {
 904                  $this->final2 = $result['merge'];
 905                  $this->_merged = &$this->final2;
 906                  return;
 907              }
 908  
 909              $result = $this->_compare_conflict_seq('final2', 'final1');
 910  
 911              if ($result['merge_found'])
 912              {
 913                  $this->_merged = &$this->final1;
 914                  return;
 915              }
 916  
 917              // Try to solve $Id$ issues. ;)
 918              if (sizeof($this->orig) == 1 && sizeof($this->final1) == 1 && sizeof($this->final2) == 1)
 919              {
 920                  $match = '#^' . preg_quote('* @version $Id: ', '#') . '[a-z\._\- ]+[0-9]+ [0-9]{4}-[0-9]{2}-[0-9]{2} [0-9\:Z]+ [a-z0-9_\- ]+\$$#';
 921  
 922                  if (preg_match($match, $this->orig[0]) && preg_match($match, $this->final1[0]) && preg_match($match, $this->final2[0]))
 923                  {
 924                      $this->_merged = &$this->final2;
 925                      return;
 926                  }
 927              }
 928  
 929              $second_run = false;
 930  
 931              // Try to solve issues where the only reason why the above did not work is a newline being removed in the final1 code but exist in the orig/final2 code
 932              if (trim($this->orig[0]) === '' && trim($this->final2[0]) === '')
 933              {
 934                  unset($this->orig[0], $this->final2[0]);
 935                  $this->orig = array_values($this->orig);
 936                  $this->final2 = array_values($this->final2);
 937  
 938                  $second_run = true;
 939              }
 940  
 941              // The same is true for a line at the end. ;)
 942              if (sizeof($this->orig) && sizeof($this->final2) && sizeof($this->orig) === sizeof($this->final2) && trim($this->orig[sizeof($this->orig)-1]) === '' && trim($this->final2[sizeof($this->final2)-1]) === '')
 943              {
 944                  unset($this->orig[sizeof($this->orig)-1], $this->final2[sizeof($this->final2)-1]);
 945                  $this->orig = array_values($this->orig);
 946                  $this->final2 = array_values($this->final2);
 947  
 948                  $second_run = true;
 949              }
 950  
 951              if ($second_run)
 952              {
 953                  $result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
 954  
 955                  if ($result['merge_found'])
 956                  {
 957                      $this->final2 = $result['merge'];
 958                      $this->_merged = &$this->final2;
 959                      return;
 960                  }
 961  
 962                  $result = $this->_compare_conflict_seq('final2', 'final1');
 963  
 964                  if ($result['merge_found'])
 965                  {
 966                      $this->_merged = &$this->final1;
 967                      return;
 968                  }
 969              }
 970  
 971              return;
 972          }
 973  
 974          // CASE TWO: Added lines from orig to final2 but final1 had added lines too. Just merge them.
 975          if (!sizeof($this->orig) && $this->final1 !== $this->final2 && sizeof($this->final1) && sizeof($this->final2))
 976          {
 977              $result = $this->_compare_conflict_seq('final2', 'final1');
 978  
 979              if ($result['merge_found'])
 980              {
 981                  $this->final2 = $this->final1;
 982                  $this->_merged = &$this->final1;
 983              }
 984              else
 985              {
 986                  $result = $this->_compare_conflict_seq('final1', 'final2');
 987  
 988                  if (!$result['merge_found'])
 989                  {
 990                      $this->final2 = array_merge($this->final1, $this->final2);
 991                      $this->_merged = &$this->final2;
 992                  }
 993                  else
 994                  {
 995                      $this->final2 = $this->final1;
 996                      $this->_merged = &$this->final1;
 997                  }
 998              }
 999  
1000              return;
1001          }
1002  
1003          // CASE THREE: Removed lines (orig has the to-remove line(s), but final1 has additional lines which does not need to be removed). Just remove orig from final1 and then use final1 as final2/merge
1004          if (!sizeof($this->final2) && sizeof($this->orig) && sizeof($this->final1) && $this->orig !== $this->final1)
1005          {
1006              $result = $this->_compare_conflict_seq('orig', 'final1');
1007  
1008              if (!$result['merge_found'])
1009              {
1010                  return;
1011              }
1012  
1013              // First of all, try to find the code in orig in final1. ;)
1014              $compare_seq = sizeof($this->orig);
1015              $begin = $end = -1;
1016              $j = 0;
1017  
1018              for ($i = 0, $size = sizeof($this->final1); $i < $size; $i++)
1019              {
1020                  $line = $this->final1[$i];
1021  
1022                  if (trim($line) === trim($this->orig[$j]))
1023                  {
1024                      // Mark begin
1025                      if ($begin === -1)
1026                      {
1027                          $begin = $i;
1028                      }
1029  
1030                      // End is always $i, the last found line
1031                      $end = $i;
1032  
1033                      if (isset($this->orig[$j+1]))
1034                      {
1035                          $j++;
1036                      }
1037                  }
1038              }
1039  
1040              if ($begin !== -1 && $begin + ($compare_seq - 1) == $end)
1041              {
1042                  foreach ($this->final1 as $i => $line)
1043                  {
1044                      if ($i < $begin || $i > $end)
1045                      {
1046                          $merged[] = $line;
1047                      }
1048                  }
1049  
1050                  $this->final2 = $merged;
1051                  $this->_merged = &$this->final2;
1052              }
1053  
1054              return;
1055          }
1056  
1057          return;
1058      }
1059  }
1060  
1061  /**
1062  * @package diff
1063  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1064  *
1065  * @access private
1066  */
1067  class diff3_op_copy extends diff3_op
1068  {
1069  	function diff3_op_copy($lines = false)
1070      {
1071          $this->orig = $lines ? $lines : array();
1072          $this->final1 = &$this->orig;
1073          $this->final2 = &$this->orig;
1074      }
1075  
1076  	function merged()
1077      {
1078          return $this->orig;
1079      }
1080  
1081  	function is_conflict()
1082      {
1083          return false;
1084      }
1085  }
1086  
1087  /**
1088  * @package diff
1089  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1090  *
1091  * @access private
1092  */
1093  class diff3_block_builder
1094  {
1095  	function diff3_block_builder()
1096      {
1097          $this->_init();
1098      }
1099  
1100  	function input($lines)
1101      {
1102          if ($lines)
1103          {
1104              $this->_append($this->orig, $lines);
1105          }
1106      }
1107  
1108  	function out1($lines)
1109      {
1110          if ($lines)
1111          {
1112              $this->_append($this->final1, $lines);
1113          }
1114      }
1115  
1116  	function out2($lines)
1117      {
1118          if ($lines)
1119          {
1120              $this->_append($this->final2, $lines);
1121          }
1122      }
1123  
1124  	function is_empty()
1125      {
1126          return !$this->orig && !$this->final1 && !$this->final2;
1127      }
1128  
1129  	function finish()
1130      {
1131          if ($this->is_empty())
1132          {
1133              return false;
1134          }
1135          else
1136          {
1137              $edit = new diff3_op($this->orig, $this->final1, $this->final2);
1138              $this->_init();
1139              return $edit;
1140          }
1141      }
1142  
1143  	function _init()
1144      {
1145          $this->orig = $this->final1 = $this->final2 = array();
1146      }
1147  
1148  	function _append(&$array, $lines)
1149      {
1150          array_splice($array, sizeof($array), 0, $lines);
1151      }
1152  }