1 | 5 | simandl | <?php |
2 | | | /** |
3 | | | * A class for computing three way diffs. |
4 | | | * |
5 | | | * $Horde: framework/Text_Diff/Diff3.php,v 1.2.10.6 2008/01/04 10:37:26 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_Diff3 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_Diff3($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_Diff3_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_Diff3_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_Diff3_Op { |
157 | | | |
158 | | | function Text_Diff3_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_Diff3_Op_copy extends Text_Diff3_Op { |
196 | | | |
197 | | | function Text_Diff3_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_Diff3_BlockBuilder { |
223 | | | |
224 | | | function Text_Diff3_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_Diff3_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 | | | } |