5 // A class for computing three way diffs
7 // Copyright (C) 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
8 // You may copy this code freely under the conditions of the GPL.
11 require_once 'lib/difflib.php';
15 public $type = 'diff3';
17 function _Diff3_Block($orig = false, $final1 = false, $final2 = false)
19 $this->orig = $orig ? $orig : array();
20 $this->final1 = $final1 ? $final1 : array();
21 $this->final2 = $final2 ? $final2 : array();
24 protected function merged()
26 if (!isset($this->_merged)) {
27 if ($this->final1 === $this->final2)
28 $this->_merged = &$this->final1;
29 elseif ($this->final1 === $this->orig)
30 $this->_merged = &$this->final2; elseif ($this->final2 === $this->orig)
31 $this->_merged = &$this->final1; else
32 $this->_merged = false;
34 return $this->_merged;
37 protected function is_conflict()
39 return $this->merged() === false;
43 class _Diff3_CopyBlock extends _Diff3_Block
45 public $type = 'copy';
47 function __construct($lines = array())
49 $this->orig = $lines ? $lines : array();
50 $this->final1 = &$this->orig;
51 $this->final2 = &$this->orig;
54 protected function merged()
59 protected function is_conflict()
65 class _Diff3_BlockBuilder
71 function __construct()
76 private function _init()
78 $this->orig = array();
79 $this->final1 = array();
80 $this->final2 = array();
83 private function _append(&$array, $lines)
85 array_splice($array, sizeof($array), 0, $lines);
88 public function input($lines)
91 $this->_append($this->orig, $lines);
94 public function out1($lines)
97 $this->_append($this->final1, $lines);
100 public function out2($lines)
103 $this->_append($this->final2, $lines);
106 private function is_empty()
108 return !$this->orig && !$this->final1 && !$this->final2;
111 public function finish()
113 if ($this->is_empty())
116 $block = new _Diff3_Block($this->orig, $this->final1, $this->final2);
125 function __construct($orig, $final1, $final2)
127 $eng = new _DiffEngine;
128 $this->ConflictingBlocks = 0; //Conflict counter
129 $this->blocks = $this->__diff3($eng->diff($orig, $final1),
130 $eng->diff($orig, $final2));
133 private function __diff3($edits1, $edits2)
136 $bb = new _Diff3_BlockBuilder;
138 $e1 = current($edits1);
139 $e2 = current($edits2);
141 if ($e1 && $e2 && $e1->type == 'copy' && $e2->type == 'copy') {
142 // We have copy blocks from both diffs. This is the (only)
143 // time we want to emit a diff3 copy block.
144 // Flush current diff3 diff block, if any
145 if ($block = $bb->finish())
148 $ncopy = min($e1->norig(), $e2->norig());
150 $blocks[] = new _Diff3_CopyBlock(array_slice($e1->orig, 0, $ncopy));
152 if ($e1->norig() > $ncopy) {
153 array_splice($e1->orig, 0, $ncopy);
154 array_splice($e1->final, 0, $ncopy);
158 if ($e2->norig() > $ncopy) {
159 array_splice($e2->orig, 0, $ncopy);
160 array_splice($e2->final, 0, $ncopy);
165 if ($e1->orig && $e2->orig) {
166 $norig = min($e1->norig(), $e2->norig());
167 $orig = array_splice($e1->orig, 0, $norig);
168 array_splice($e2->orig, 0, $norig);
172 if ($e1->type == 'copy')
173 $bb->out1(array_splice($e1->final, 0, $norig));
175 if ($e2->type == 'copy')
176 $bb->out2(array_splice($e2->final, 0, $norig));
178 if ($e1 && !$e1->orig) {
179 $bb->out1($e1->final);
182 if ($e2 && !$e2->orig) {
183 $bb->out2($e2->final);
189 if ($block = $bb->finish())
195 public function merged_output($label1 = '', $label2 = '')
198 foreach ($this->blocks as $block) {
199 if ($block->is_conflict()) {
200 // FIXME: this should probably be moved somewhere else...
201 $lines = array_merge($lines,
202 array("<<<<<<<" . ($label1 ? " $label1" : '')),
206 array(">>>>>>>" . ($label2 ? " $label2" : '')));
207 $this->ConflictingBlocks++;
209 $lines = array_merge($lines, $block->merged());