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 | ?>
|
---|