[Summary view] [Print] [Text view]

   1  <?php
   2  /**
   3   * A class for computing three way diffs.
   4   *
   5   * $Horde: framework/Text_Diff/Diff/ThreeWay.php,v 1.3.2.3 2008/01/04 10:37:27 jan Exp $
   6   *
   7   * Copyright 2007-2008 The Horde Project (http://www.horde.org/)
   8   *
   9   * See the enclosed file COPYING for license information (LGPL). If you did
  10   * not receive this file, see http://opensource.org/licenses/lgpl-license.php.
  11   *
  12   * @package Text_Diff
  13   * @since   0.3.0
  14   */
  15  
  16  /** Text_Diff */
  17  require_once 'Text/Diff.php';
  18  
  19  /**
  20   * A class for computing three way diffs.
  21   *
  22   * @package Text_Diff
  23   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  24   */
  25  class Text_Diff_ThreeWay extends Text_Diff {
  26  
  27      /**
  28       * Conflict counter.
  29       *
  30       * @var integer
  31       */
  32      var $_conflictingBlocks = 0;
  33  
  34      /**
  35       * Computes diff between 3 sequences of strings.
  36       *
  37       * @param array $orig    The original lines to use.
  38       * @param array $final1  The first version to compare to.
  39       * @param array $final2  The second version to compare to.
  40       */
  41      function Text_Diff_ThreeWay($orig, $final1, $final2)
  42      {
  43          if (extension_loaded('xdiff')) {
  44              $engine = new Text_Diff_Engine_xdiff();
  45          } else {
  46              $engine = new Text_Diff_Engine_native();
  47          }
  48  
  49          $this->_edits = $this->_diff3($engine->diff($orig, $final1),
  50                                        $engine->diff($orig, $final2));
  51      }
  52  
  53      /**
  54       */
  55      function mergedOutput($label1 = false, $label2 = false)
  56      {
  57          $lines = array();
  58          foreach ($this->_edits as $edit) {
  59              if ($edit->isConflict()) {
  60                  /* FIXME: this should probably be moved somewhere else. */
  61                  $lines = array_merge($lines,
  62                                       array('<<<<<<<' . ($label1 ? ' ' . $label1 : '')),
  63                                       $edit->final1,
  64                                       array("======="),
  65                                       $edit->final2,
  66                                       array('>>>>>>>' . ($label2 ? ' ' . $label2 : '')));
  67                  $this->_conflictingBlocks++;
  68              } else {
  69                  $lines = array_merge($lines, $edit->merged());
  70              }
  71          }
  72  
  73          return $lines;
  74      }
  75  
  76      /**
  77       * @access private
  78       */
  79      function _diff3($edits1, $edits2)
  80      {
  81          $edits = array();
  82          $bb = new Text_Diff_ThreeWay_BlockBuilder();
  83  
  84          $e1 = current($edits1);
  85          $e2 = current($edits2);
  86          while ($e1 || $e2) {
  87              if ($e1 && $e2 && is_a($e1, 'Text_Diff_Op_copy') && is_a($e2, 'Text_Diff_Op_copy')) {
  88                  /* We have copy blocks from both diffs. This is the (only)
  89                   * time we want to emit a diff3 copy block.  Flush current
  90                   * diff3 diff block, if any. */
  91                  if ($edit = $bb->finish()) {
  92                      $edits[] = $edit;
  93                  }
  94  
  95                  $ncopy = min($e1->norig(), $e2->norig());
  96                  assert($ncopy > 0);
  97                  $edits[] = new Text_Diff_ThreeWay_Op_copy(array_slice($e1->orig, 0, $ncopy));
  98  
  99                  if ($e1->norig() > $ncopy) {
 100                      array_splice($e1->orig, 0, $ncopy);
 101                      array_splice($e1->final, 0, $ncopy);
 102                  } else {
 103                      $e1 = next($edits1);
 104                  }
 105  
 106                  if ($e2->norig() > $ncopy) {
 107                      array_splice($e2->orig, 0, $ncopy);
 108                      array_splice($e2->final, 0, $ncopy);
 109                  } else {
 110                      $e2 = next($edits2);
 111                  }
 112              } else {
 113                  if ($e1 && $e2) {
 114                      if ($e1->orig && $e2->orig) {
 115                          $norig = min($e1->norig(), $e2->norig());
 116                          $orig = array_splice($e1->orig, 0, $norig);
 117                          array_splice($e2->orig, 0, $norig);
 118                          $bb->input($orig);
 119                      }
 120  
 121                      if (is_a($e1, 'Text_Diff_Op_copy')) {
 122                          $bb->out1(array_splice($e1->final, 0, $norig));
 123                      }
 124  
 125                      if (is_a($e2, 'Text_Diff_Op_copy')) {
 126                          $bb->out2(array_splice($e2->final, 0, $norig));
 127                      }
 128                  }
 129  
 130                  if ($e1 && ! $e1->orig) {
 131                      $bb->out1($e1->final);
 132                      $e1 = next($edits1);
 133                  }
 134                  if ($e2 && ! $e2->orig) {
 135                      $bb->out2($e2->final);
 136                      $e2 = next($edits2);
 137                  }
 138              }
 139          }
 140  
 141          if ($edit = $bb->finish()) {
 142              $edits[] = $edit;
 143          }
 144  
 145          return $edits;
 146      }
 147  
 148  }
 149  
 150  /**
 151   * @package Text_Diff
 152   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 153   *
 154   * @access private
 155   */
 156  class Text_Diff_ThreeWay_Op {
 157  
 158      function Text_Diff_ThreeWay_Op($orig = false, $final1 = false, $final2 = false)
 159      {
 160          $this->orig = $orig ? $orig : array();
 161          $this->final1 = $final1 ? $final1 : array();
 162          $this->final2 = $final2 ? $final2 : array();
 163      }
 164  
 165      function merged()
 166      {
 167          if (!isset($this->_merged)) {
 168              if ($this->final1 === $this->final2) {
 169                  $this->_merged = &$this->final1;
 170              } elseif ($this->final1 === $this->orig) {
 171                  $this->_merged = &$this->final2;
 172              } elseif ($this->final2 === $this->orig) {
 173                  $this->_merged = &$this->final1;
 174              } else {
 175                  $this->_merged = false;
 176              }
 177          }
 178  
 179          return $this->_merged;
 180      }
 181  
 182      function isConflict()
 183      {
 184          return $this->merged() === false;
 185      }
 186  
 187  }
 188  
 189  /**
 190   * @package Text_Diff
 191   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 192   *
 193   * @access private
 194   */
 195  class Text_Diff_ThreeWay_Op_copy extends Text_Diff_ThreeWay_Op {
 196  
 197      function Text_Diff_ThreeWay_Op_Copy($lines = false)
 198      {
 199          $this->orig = $lines ? $lines : array();
 200          $this->final1 = &$this->orig;
 201          $this->final2 = &$this->orig;
 202      }
 203  
 204      function merged()
 205      {
 206          return $this->orig;
 207      }
 208  
 209      function isConflict()
 210      {
 211          return false;
 212      }
 213  
 214  }
 215  
 216  /**
 217   * @package Text_Diff
 218   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 219   *
 220   * @access private
 221   */
 222  class Text_Diff_ThreeWay_BlockBuilder {
 223  
 224      function Text_Diff_ThreeWay_BlockBuilder()
 225      {
 226          $this->_init();
 227      }
 228  
 229      function input($lines)
 230      {
 231          if ($lines) {
 232              $this->_append($this->orig, $lines);
 233          }
 234      }
 235  
 236      function out1($lines)
 237      {
 238          if ($lines) {
 239              $this->_append($this->final1, $lines);
 240          }
 241      }
 242  
 243      function out2($lines)
 244      {
 245          if ($lines) {
 246              $this->_append($this->final2, $lines);
 247          }
 248      }
 249  
 250      function isEmpty()
 251      {
 252          return !$this->orig && !$this->final1 && !$this->final2;
 253      }
 254  
 255      function finish()
 256      {
 257          if ($this->isEmpty()) {
 258              return false;
 259          } else {
 260              $edit = new Text_Diff_ThreeWay_Op($this->orig, $this->final1, $this->final2);
 261              $this->_init();
 262              return $edit;
 263          }
 264      }
 265  
 266      function _init()
 267      {
 268          $this->orig = $this->final1 = $this->final2 = array();
 269      }
 270  
 271      function _append(&$array, $lines)
 272      {
 273          array_splice($array, sizeof($array), 0, $lines);
 274      }
 275  
 276  }