1: <?php
  2: /**
  3:  * A class for computing three way merges.
  4:  *
  5:  * Copyright 2007-2012 Horde LLC (http://www.horde.org/)
  6:  *
  7:  * See the enclosed file COPYING for license information (LGPL). If you did
  8:  * not receive this file, see http://www.horde.org/licenses/lgpl21.
  9:  *
 10:  * @package Text_Diff
 11:  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 12:  */
 13: class Horde_Text_Diff_ThreeWay
 14: {
 15:     /**
 16:      * Array of changes.
 17:      *
 18:      * @var array
 19:      */
 20:     protected $_edits;
 21: 
 22:     /**
 23:      * Conflict counter.
 24:      *
 25:      * @var integer
 26:      */
 27:     protected $_conflictingBlocks = 0;
 28: 
 29:     /**
 30:      * Computes diff between 3 sequences of strings.
 31:      *
 32:      * @param array $orig    The original lines to use.
 33:      * @param array $final1  The first version to compare to.
 34:      * @param array $final2  The second version to compare to.
 35:      */
 36:     public function __construct($orig, $final1, $final2)
 37:     {
 38:         if (extension_loaded('xdiff')) {
 39:             $engine = new Horde_Text_Diff_Engine_Xdiff();
 40:         } else {
 41:             $engine = new Horde_Text_Diff_Engine_Native();
 42:         }
 43: 
 44:         $this->_edits = $this->_diff3($engine->diff($orig, $final1),
 45:                                       $engine->diff($orig, $final2));
 46:     }
 47: 
 48:     /**
 49:      */
 50:     public function mergedOutput($label1 = false, $label2 = false)
 51:     {
 52:         $lines = array();
 53:         foreach ($this->_edits as $edit) {
 54:             if ($edit->isConflict()) {
 55:                 /* FIXME: this should probably be moved somewhere else. */
 56:                 $lines = array_merge($lines,
 57:                                      array('<<<<<<<' . ($label1 ? ' ' . $label1 : '')),
 58:                                      $edit->final1,
 59:                                      array("======="),
 60:                                      $edit->final2,
 61:                                      array('>>>>>>>' . ($label2 ? ' ' . $label2 : '')));
 62:                 $this->_conflictingBlocks++;
 63:             } else {
 64:                 $lines = array_merge($lines, $edit->merged());
 65:             }
 66:         }
 67: 
 68:         return $lines;
 69:     }
 70: 
 71:     /**
 72:      */
 73:     protected function _diff3($edits1, $edits2)
 74:     {
 75:         $edits = array();
 76:         $bb = new Horde_Text_Diff_ThreeWay_BlockBuilder();
 77: 
 78:         $e1 = current($edits1);
 79:         $e2 = current($edits2);
 80:         while ($e1 || $e2) {
 81:             if ($e1 && $e2 &&
 82:                 $e1 instanceof Horde_Text_Diff_Op_Copy &&
 83:                 $e2 instanceof Horde_Text_Diff_Op_Copy) {
 84:                 /* We have copy blocks from both diffs. This is the (only)
 85:                  * time we want to emit a diff3 copy block.  Flush current
 86:                  * diff3 diff block, if any. */
 87:                 if ($edit = $bb->finish()) {
 88:                     $edits[] = $edit;
 89:                 }
 90: 
 91:                 $ncopy = min($e1->norig(), $e2->norig());
 92:                 assert($ncopy > 0);
 93:                 $edits[] = new Horde_Text_Diff_ThreeWay_Op_Copy(array_slice($e1->orig, 0, $ncopy));
 94: 
 95:                 if ($e1->norig() > $ncopy) {
 96:                     array_splice($e1->orig, 0, $ncopy);
 97:                     array_splice($e1->final, 0, $ncopy);
 98:                 } else {
 99:                     $e1 = next($edits1);
100:                 }
101: 
102:                 if ($e2->norig() > $ncopy) {
103:                     array_splice($e2->orig, 0, $ncopy);
104:                     array_splice($e2->final, 0, $ncopy);
105:                 } else {
106:                     $e2 = next($edits2);
107:                 }
108:             } else {
109:                 if ($e1 && $e2) {
110:                     if ($e1->orig && $e2->orig) {
111:                         $norig = min($e1->norig(), $e2->norig());
112:                         $orig = array_splice($e1->orig, 0, $norig);
113:                         array_splice($e2->orig, 0, $norig);
114:                         $bb->input($orig);
115:                     }
116: 
117:                     if ($e1 instanceof Horde_Text_Diff_Op_Copy) {
118:                         $bb->out1(array_splice($e1->final, 0, $norig));
119:                     }
120: 
121:                     if ($e2 instanceof Horde_Text_Diff_Op_Copy) {
122:                         $bb->out2(array_splice($e2->final, 0, $norig));
123:                     }
124:                 }
125: 
126:                 if ($e1 && ! $e1->orig) {
127:                     $bb->out1($e1->final);
128:                     $e1 = next($edits1);
129:                 }
130:                 if ($e2 && ! $e2->orig) {
131:                     $bb->out2($e2->final);
132:                     $e2 = next($edits2);
133:                 }
134:             }
135:         }
136: 
137:         if ($edit = $bb->finish()) {
138:             $edits[] = $edit;
139:         }
140: 
141:         return $edits;
142:     }
143: }
144: