[Summary view] [Print] [Text view]

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