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